Check Whether the Given no. is Prime or Not using C | C Program

Here's a C program to check whether a given number is prime number or not with output and proper explanation. This program uses C concepts like break statement, modulus in C, IF-ELSE conditions and for loops.

What's a Prime Number? A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

# include <stdio.h>
# include <conio.h>
void main() 
{ 
 int i, n, flag = 0 ; 
 clrscr() ; 
 printf("Enter the Number : ") ; 
 scanf("%d", &n) ; 
 if(n <= 3) 
  flag = 0 ; 
 else 
 { 
  for(i = 2 ; i <= n / 2 ; i++) 
   if(n % i == 0) 
   { 
    flag = 1 ; 
    break ; 
   } 
 } 
 if(flag == 1) 
  printf("\nThe number is not prime") ; 
 else 
  printf("\nThe number is prime") ; 
 getch() ; 
} 

Output of above program 

Enter the number : 15
The number is not prime

Enter the number : 7
The number is prime.


Explanation of above program

We  have three integer variables here -

• n - is the number which we're checking to be prime.
• i - is the loop variable.
• flag - is a tracking variable. Its value is initially set to 0 and if after the completion of program its value is still 0 that means the number we entered is a prime number.

Tip : To check for a prime number we just need to check whether a number n is divisible by any number between 2 and n / 2. It is obvious because no number can be divisible by a number which is greater than its half e.g. all divisors of 18 are less than or equal to 9 i.e. half of 18. This is also true for each number. So we can reduce our for loop by half number of total iterations. Also, we can skip the checking for 1, 2 and 3 using the IF condition, setting the flag variable to 0 i.e. that number is a prime number.

In the else part we've a for loop looping for i = 2 to n / 2. Inside for loop, we check whether our number is divisible by any value of loop variable by the following expression in the IF condition - n % i == 0. If this value becomes true for any value of i, the if part is executed then the flag is set to 1 (indicating the number is not prime) and using break statement we terminate our loop. Also if our number is a prime number, the IF condition inside the for loop will never become true and value of flag variable will be 0 i.e. indicating that the number is a prime number.

Outside the for loop and else condition, we've another IF-Else condition. This is used to check the value of flag i.e. IF the value of flag is 1 the number is not prime otherwise the number is prime.