Check If A Number Is A Prime Number

Tuesday, September 10, 2013 Vinster 5 Comments A⁺ a^-

Problem:

Write a C++ program which checks if a number is a prime number or not?

A prime number is any natural number greater than 1 with no other positive factors other than 1 and itself.

Let's take 5 as an example:

1 and 5 (the number itself) can evenly divide 5 so they are factors of 5.
2, 3, 4 are cannot evenly divide 5 so they are not factors of 5.
Therefore, 5 is a Prime Number.

The program below shows a number is asked and it is evaluated if a prime number or not.

Logic:
Let us start checking for its factors from 2 until the number itself. A factor is a number which can evenly divide the number thus it is checked if the remainder (modulus result) is 0. Every time a factor is seen, it is counted through a counter name countFactors.

When the loop ends, countFactors is checked.
If countFactors is equal to 1, meaning no other factor is found except for the number itself, it is a prime number. If countFactors is greater than 1, then it is not a prime number.

/*
Prime Number
Check if a number is a prime number or not.
*/
#include <iostream>

using namespace std;

int main(void)
{
 //variables
 int number,i,countFactors;
 char hang;

 cout << "Enter the number: ";
 cin >> number;
 
 countFactors = 0;
 for (i = 2; i <= number; i++)
 {
  //if a factor exists from 2 up to the number, count Factors
  if (number % i == 0)
  {
   countFactors++;    
  }
 }

 //a prime number has only itself as a factor other than 1
 if (countFactors == 1)
  {
  cout << number << " is a Prime Number." <<endl;
 }
 else
 {
  cout << number << " is not a prime number but a composite number." << endl;
 }
 
 //to let console stay
 cin >> hang;

 return 0;
}

Enter the number: 6
6 is not a prime number but a composite number.

If you want to have a logic to minimize the loop, you can check if the factor is lesser than the number. If the factor is lesser than the number, break the loop to minimize processing time. It will not continue checking for other factors because it is already found that there is other factor other than the number,thus it is not a prime number.

countFactors = 0;
 for (i = 2; i <= number; i++)
 {
  cout << i << ",";
  //if a factor exists from 2 up to the number, count Factors
  if (number % i == 0)
  {
   countFactors++;    

   //break loop if a factor is lesser than the number
   if (i < number)
   {
    countFactors = 2;
    break;
   }
  }
 }

5 comments

Write comments

Unknown

AUTHOR

November 21, 2013 at 12:40 AM delete

Nice solution, but your one optimization does not do anything. i is of course smaller than number, that is what you check in your for loop. The first optimization step should be, that i only goes up until half of number, e. g. i <= (number/2). Because any i bigger than that would have to be multiplied by a factor smaller than 2 to get to number.

Vinster

December 9, 2013 at 3:13 PM delete

Hi Patryk, thanks for you comment. I really appreciate it and will take a look at your solution and then share to others.

Thanks a lot!

July 13, 2017 at 6:15 AM delete

Get various ways to finds the prime numbers with new methods such as mathematical formula , c++ , c etc . You can also download materials to know more about prime numbers.