C program to find prime number efficient in less time

C program to find prime number efficient in less time: This C program will find the given number is prime number with less time, by testing whether the given number is a multiple of any integer between 2 and square root of that number. While you can find prime number with c program easily without much computation. You can also refer to find the prime number c program using recursion. But this program makes computation of prime number with less time complexity.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.

C program to find prime number efficient in less time

#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();
}

output of C program to find prime number efficient in less time

: