# C Program to Check if a Number is Prime

Write a program in c to check if a number is prime or not.

For example,

Input
7
Output
7 is prime

Input
14
Output
14 is not prime

Prime Number: A positive number that is divisible by exactly 2 numbers – by 1 and by itself. For example, 13. 13 is only divisible by 1 and 13. Thus, 13 is prime.
Note: 1 is not a prime number because it is divisible by only 1 number that is 1.

## Naive Approach

Let N be the input number. The simplest way to check if N is prime or not is to traverse all the numbers in the range [2, N-1] and check if any of them divides N. If any number do divide N, then it means N is divisible by more than 2 numbers. Thus, N is not a prime.

#include<stdio.h>

int main() {
int i,flag;
int n; // input

printf("Enter to number to check if it is prime or not: ");
scanf("%d",&n);

if(n==1){
printf("%d is prime",n);
}
else{

flag = 0;
for(i = 2;i<=n-1;++i){
if(n%i==0){
// this segment of code runs if
// n is divisible by i
// thus n is not prime
// we set flag to 1 and break the loop
flag=1;
break;
}
}

if(flag==1)
printf("%d is not prime",n);
else
printf("%d is prime",n);

}
}

Output

Enter to number to check if it is prime or not: 45
45 is not prime

## Efficient Approach

In the above code, the loop ranges from 2 to N-1 but it’s unnecessary. No divisor of N can be greater than N/2. The only number greater than N/2 that can divide N is N itself.

Therefore, we change the loop range from [2, N-1] to [2, N/2].

#include<stdio.h>

int main() {
int i,flag;
int n; // input

printf("Enter to number to check if it is prime or not: ");
scanf("%d",&n);

if(n==1){
printf("%d is prime",n);
}
else{

flag = 0;
for(i = 2;i<=n/2;++i){
if(n%i==0){
flag=1;
break;
}
}

if(flag==1)
printf("%d is not prime",n);
else
printf("%d is prime",n);

}
}

Output

Enter to number to check if it is prime or not: 29
29 is prime

## More Efficient Approach

The above 2 code works fine if the input is small N ~ 106 but if the input is greater than 109 then performance may suffer.

We can optimize the code further. Instead of looking for divisor in the range [2, N/2], we can change the range to [2, SquareRoot(N)].

Let X be the square root of N. Then All divisors of N should be in form Both p and q cannot be greater than X, it will result in p*q > N. Similarly, both p and q cannot be smaller than X, it will result in p*q < N.

Therefore, we can say that . In simple words, if a number is a divisor of N then there exists another number that is also a divisor of N. Thus, we don’t have to loop beyond X to check if a number divides N or not.

#include<stdio.h>
#include<math.h>
int main() {
int i,flag;
int n; // input

printf("Enter to number to check if it is prime or not: ");
scanf("%d",&n);

if(n==1){
printf("%d is prime",n);
}
else{

flag = 0;
for(i = 2;i<=sqrt(n);++i){
if(n%i==0){
flag=1;
break;
}
}

if(flag==1)
printf("%d is not prime",n);
else
printf("%d is prime",n);

}
}

Output

Enter to number to check if it is prime or not: 1231
1231 is prime