c program to find prime number efficiently in less time ?

This C program will find the given number is prime with less time, by testing whether the given number is a multiple of any integer between 2 and square root of that number. Lets take an example to understand this. Suppose the number is 21, then rather to check its divisibility from 2 to 20, just test it divisibility only by 2, 3, and 4.As square of 4 is 16 and that of 5 is 25 which is greater than 21. The below program will let you know how this is done.

#include<stdio.h>
#include<conio.h>

int main()
{
     int n;
     int i,s=1,p=1;
     printf("enter the number :");
     scanf("%d",&n);
     while(p<n)
     {
     s++;
     p=s*s;
     }
     printf("\nDivisibility is checked till number %d \n\n",s-1);
     for(i=2; i<s; i++)
     {
              if(n%i==0)
               {
                printf("%d is not a prime number", n);
               getch();
               return (1);
               }
      }
printf("%d is a prime number", n);
getch();
}
        
    

Here is the output :

 find prime number efficiently in less time

If you like this post then consider sharing it with others.