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,

13 is a *Prime Number*, because 13 is not divisible by any number other than 1 and 13.

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<stdio.h> #include<conio.h> #include<math.h> void main() { int n, i=2, flag=0; clrscr(); printf("nn Enter a positive integer value: "); scanf("%d",&n); /* Loop to check whether 'n' is divisible by any number between 2 and sqrt(n) */ while(i<=sqrt(n)) { if(n%i==0) { flag=1; break; } i++; } /* if else condition to print Prime Number or Not */ if (flag==0) printf("n %d is a prime number.",n); else printf("n %d is not a prime number.",n); getch(); }

**Related: Prime number or Not in C using For Loop**

## Working:

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

## Step by Step working of the above Program Code:

**For Prime Number:**

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

3.1. i<=sqrt(n) (2<=√11) while loop condition is true

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

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

3.2. i<=sqrt(n) (3<=√11) while loop condition is true

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

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

3.3. i<=sqrt(n) (4<=√11) while loop condition is false

It comes out of the while loop.

- flag==0 (0==0) if condition is true

So it prints 11 is a prime number.

- Thus program execution is completed.

**For Not a Prime Number:**

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

3.1. i<=sqrt(n) (2<=√15) while loop condition is true

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

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

3.2. i<=sqrt(n) (3<=√15) while loop condition is true

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

It assigns flag=1

breaks the loop and comes out of the while loop

- flag==0 (1==0) if condition is false

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

- Thus program execution is completed.