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

For example,

Input7Output7 is primeInput14Output14 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 ~ 10^{6} but if the input is greater than 10^{9} 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

**Read**

Right Shift Array by One

Find all Subset of Array in C++

Reverse a string in C without string functions (using both loop and recursion)