FIND A NUMBER IS PRIME OR NOT

METHOD 1:

#include <stdio.h>
int main()
{
  int n, i, flag=0;
  printf("Enter a positive integer: ");
  scanf("%d",&n);
  for(i=2;i<=n/2;++i)
  {
      if(n%i==0)
      {
          flag=1;
          break;
      }
  }
  if (flag==0)
      printf("%d is a prime number.",n);
  else
      printf("%d is not a prime number.",n);
  return 0;
}

METHOD 2:

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.

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