# Program to check whether a number is prime or not in C

Before we check whether a number is prime or not, we should know the answer for the question "What is a prime number ?"
Definition : A number which is only divisible by 1 and itself is a prime number. For example, numbers such as 1, 2, 3, 5, 7, 11 etc. are not divisible by any numbers other than 1 and themselves. So, they are all prime numbers. But, the numbers such as 4, 6, 8, 16 etc., are divisible by 2 and hence they are non-prime numbers. The number 9 is divisible by 3 and hence it is also no-prime number. Now, let us see " How to check whether a given number is prime or not?"

Procedure : Consider the number 16. It is not divisible by 9, 10, 11, 12, 13, 14 and 15 which are all greater than 16/2. So, the first point to remember is:
• A number m cannot be divisible by a number which is greater than m / 2.
In our case m is 16. It is divisible by the numbers 2, 4 and 8 which are less than or equal to 16/2.
The second point to remember is:
• A number m may be only divisible by either 2 or 3 or 4 or 5 ..... or m/2.
So, to check whether m is prime or not, it is sufficient to divide m by the numbers 2, 3, 4....m/2 one after the other. During this process, if the remainder is zero, the number m is non-prime.
But, even after dividing m by all the numbers from 2 to m/2, if the remainder is still not zero, the number m is prime.
The partial code is as follows
for (i=2; i<=m/2; i++)
{

if(m%i == 0)
{
printf("The number is non-prime");
exit(0);
}

}
printf("The number is prime\n");

The algorithm and the equivalent flowchart are shown below:
Algorithm : PRIME
[This algorithm checks whether the given number is prime or not.]

Step 1: [Enter the number]
Step 2: [Check for prime number]
for i=2 to n/2 in step 1
if(n%i == 0)
Write : 'Number is non-prime'
Exit.
[End of if]
[End of for]
Step 3: [Output prime]
Write: 'number is prime'
Step 4: [finished]
Exit.

The complete program to check whether the given number is prime or not is shown below:
Example : Program to check whether a number is prime or not.

Program
#include<stdio.h>
#include<stdlib.h>
main( )
{
int n, i;
printf("Enter a number:\n");
scanf("%d",&n);
for(i=2; i<=n/2; i++)
{
if(n%i == 0)
{
printf("%d is non-prime",n);
exit(0);
}
}
printf("%d is prime",n);
}

TRACE 1

Input
Enter a number
13
Computations
i=2 3 4 5 6
13/2  13/3  13/4  13/5 13/6
2,3,4,5,6 can't divide 13
Output
13 is prime

TRACE 2

Input
Enter a number:
9
Computations
i=2 3 4
9/2  9/3

Output
9 is non-prime

Some say he’s half man half fish, others say he’s more of a seventy/thirty split. Either way he’s a fishy bastard. Google