C++ Program to check a number is prime or not


January 18, 2023, Learn eTutorial
1485

Here in this C++ program, we are checking whether a user input is a prime number or not.

What is a prime number?

 A prime number or prime integer, (often simply called a "prime" for short) is a positive integer that has no divisors other than 1 and that number itself. 

E.g. 2, 3, 5, 7, 11. Let us take the number '5' is a prime number because the number '5' has only two divisors: '1' and '5'. So the prime number has two divisors only. But, 4 is not prime (it is composite) since 2 x 2 = 4.

Note:  the number '1' is not a prime number as it has only one divisor.

Prime Number

How to implement checking for prime numbers in C++?

Take a positive integer from the user and store it in the variable n. At the beginning set a Boolean variable is_prime to true. 0 and 1 are not prime numbers, so first we have to check if the input number is 0 or 1. If the number is either 0 or 1 then the value of is_prime is set to false.


if ( n= 0 // n=1 )
{ 
   is_prime = false 
}
 

Else the value of is_prime remains unchanged. Ie; is_prime = true;

Then check whether the number is perfectly divisible by other numbers or not. This can be done with the help of a for  loop. Initialize the value of i =2. The loop will start from 'i =2' to 'i <= n/2' and increases the value of 'i' by '1' with each iteration. The loop terminates at 'i= n/2' because we cannot find any factor for n beyond the number 'n/2'. If the number entered by the user is perfectly divisible by 'i', then is_prime is set to false and the number will not be a prime number. We use the mod operator to check the number divisibility in a if condition 'n % i == 0'.

But if the entered number is not perfectly divisible by 'i' throughout the entire loop, then it means that the input is only divisible by '1' and that number itself. So, the given input is a prime number.

Algorithm 

Step 1:  Call the header file iostream.

Step 2: Use the namespace std.

Step 3: Open the main()

Step 4: Declare integer type variable n; Initialise a Boolean variable is_prime to true

Step 5: Print a message to enter a positive integer.

Step 6: Read the character into the variable n;

Step 7: Check whether the entered number is 0 or 1. If true, print n is not a prime number

Step 8: else, execute the loop to check if n is prime.

Step 9: initialize i=2 and continue the loop until i<= n/2;

Step 10: check if (n % i= 0 ) 

Step 11: if yes set is_prime = false;

Step 12: print n as a prime number if is_prime is true

Step 13: else print n is not a prime number

Step 14: Exit.

C++ Source Code

                                          #include <iostream>
using namespace std;

int main() {

  int i, n;
  bool is_prime = true;

  cout << "Enter a positive integer: ";
  cin >> n;

  // 0 and 1 are not prime numbers
  if (n == 0 || n == 1) {
    is_prime = false;
  }

  // loop to check if n is prime
  for (i = 2; i <= n/2; ++i) {
    if (n % i == 0) {
      is_prime = false;
      break;
    }
  }

  if (is_prime)
    cout << n << " is a prime number";
  else
    cout << n << " is not a prime number";

  return 0;
}
                                      

OUTPUT

Enter a positive integer: 8
8 is not a prime number
Run 2 
Enter a positive integer: 5
5 is a prime number