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 )



Related Contents to follow