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");
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'
[End of if]
[End of for]
Step 3: [Output prime]
Write: 'number is prime'
Step 4: [finished]
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.
int n, i;
printf("Enter a number:\n");
for(i=2; i<=n/2; i++)
if(n%i == 0)
printf("%d is non-prime",n);
printf("%d is prime",n);
Enter a number
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
13 is prime
Enter a number:
i=2 3 4
9 is non-prime