# write a c program to check if number is prime number

A prime number is number that can be divided only by 1 and itself.The only even prime number is 2. All other even numbers can be divided by 2.Zero and 1 are not considered prime numbers.Except for 0 and 1, a number is either a prime number or a composite number. A composite number is defined as any number, greater than 1, that is not prime.

Based on the above facts below is unoptimized simple c code which can be used to test prime number:

```
#include<stdio.h>
int main()
{
int i,num;
printf("Enter a number: ");
scanf("%d",&num);
i=2;
while(i<=num/2)
{
if(num%i==0)
{
printf("Not a Prime number \n");
break;
}
i++;
}
if(i==(num/2)+1)
printf("Prime number \n");
return 0;
}
```

But if number is very large then this will take much more time. so lets write a better program for prime checking. here is some efficient algorithm for prime number testing:

## Fermat Primality Test

According to Fermat’s Little Theorem if p is a prime number and a is a positive integer less than p, then

a^{p}= a ( mod p ) or alternatively: a^{(p-1)}= 1 ( mod p )

## Leave a Reply