• • 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

```    ap = a ( mod p )
or alternatively:
a(p-1) = 1 ( mod p )

```