Before going to the program for Prime Number or Not first let us understand what is a Prime Number?

Prime Number:

                 A Prime Number is a number greater than 1 and which is only divisible by 1 and the number itself.

For example,

                19 is a Prime Number because 19 is not divisible by any number other than 1 and 19.

To find whether a Number is Prime Number or Not it is enough to check whether ‘n’ is divisible by any number between 2 and √n. If it is divisible then ‘n’ is not a Prime Number otherwise it is a Prime Number.

Related: C Program to display Prime Numbers between Two Intervals

Program code for Prime Number or Not in C++:

/* Prime Number or Not */
#include<iostream.h>
#include<conio.h>
#include<math.h>

void main()
{
    int n, flag=0;
    clrscr();

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

    /* Loop to check whether 'n' is divisible by any number between 2 and sqrt(n) */
    for(i=2; i<=sqrt(n); i++)
    {
        if(n%i==0)
        {
           flag=1;
           break;
        }
    }
    /* if else condition to print Prime Number or Not */
    if (flag==0)
        cout<<n<<" is a prime number.";
    else
        cout<<n<<" is not a prime number.";

    getch();
}

Related: Prime number or Not in C++ using While Loop

Working:

• First, the computer reads the positive integer value from the user.
• Then using for loop it checks whether ‘n’ is divisible by any number between 2 and √n.
• Finally, the if else condition is used to print whether the number is a prime number or not.

Step by Step working of the above Program Code:

For Prime Number:

1. Let us assume that a user enters the positive integer value as 19.
2. It assigns the value of flag=0, n=19.
3. It assigns the value of i=2 and the loop continues till the condition of the for loop is true.

3.1.   i<=sqrt(n)    (2<=√19)    for loop condition is true

n%i==0    (19%2==0)    if condition is false

i++            (i=i+1)     So  i=3

3.2.   i<=sqrt(n)    (3<=√19)   for loop condition is true

n%i==0    (19%3==0)    if condition is false

i++            (i=i+1)     So  i=4

3.3.   i<=sqrt(n)    (4<=√19)   for loop condition is true

n%i==0    (19%4==0)    if condition is false

i++            (i=i+1)     So  i=5

3.4.   i<=sqrt(n)    (5<=√19)   for loop condition is false

It comes out of the for loop.

4. flag==0    (0==0)    if condition is true

So it prints, 19 is a prime number.

5. Thus program execution is completed.

For Not a Prime Number:

1. Let us assume that a user enters the positive integer value as 18.
2. It assigns the value of flag=0, n=18.
3. It assigns the value of i=2 and the loop continues till the condition of the for loop is true.

3.1.   i<=sqrt(n)    (2<=√18)   for loop condition is true

n%i==0    (18%2==0)    if condition is false

i++            (i=i+1)     So  i=3

3.2.   i<=sqrt(n)    (3<=√18)   for loop condition is true

n%i==0    (18%3==0)    if condition is true

It assigns flag=1

breaks the loop and comes out of the for loop

4. flag==0    (1==0)    if condition is false

So it goes to the else part and prints 18 is not a prime number.

5. Thus program execution is completed.

Output: