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:

int main()
     int i,num;
     printf("Enter a number: ");
              printf("Not a Prime number \n");
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 )

Related Contents to follow