Effective Way to test Number is Prime or Not .

Prime number is one of most frequent thing we face in programming  Problems . But you know most time we use algorithm to test number is prime or not is is very slow if number is too big . In other word our algorithm is not efficient .

But little bit change to that algorithm make it more efficient .

Prime number : 

A integer that has no integral factor except 1 and itself . ( 1 is not treated as prime number )

Now normal Way to solve this is make a for loop from 2 to N/2 & check divisibility for each integer .

Take a look of C code :

Related Post : How to host your website for FREE (google drive )

// check given no is prime or NOt

#include<stdio.h>


void check_prime(int N)
{
      int i,flag=0;
      for(i=2;i<=N/2;i++) //check for each num between 2 & n/2
      {
          if(N%i == 0)
              {
                  flag=1;
                  break;
              }
    }
    if(flag==0)
       printf("\nPrime");
    else
     printf("\n NOt Prime");
}

void main()
{
    int N;
    printf("Enter No to Check : ");
    scanf("%d",&N);
    
    check_prime(N); //call function to check
}




OutPut :

Now lets Modify above Program to increase its speed . i.e. number of steps .

Let number Be N
and let say it is Not prime number than N = a*b where a and b less than or equal to squre  root of N
i.e. a,b <= sqrt(N)   (Why ...???) this is basic mathematics .. So you have to interpret it by yourself .if you find out comment here with your reason .

Now you can modify above code i.e check its divisibility in range 2 to sqrt(N).

Related Post :  Php crash course Get POST & REQUEST

C code : 

// check given no is prime or NOt

#include<stdio.h>
#include<math.h>

void ch_prime(int N)
{
      int i,sq,flag=0;
      sq=sqrt(N);      //finding squire root 
      for(i=2;i<=sq;i++)
      {
          if(N%i == 0)
              {
                  flag=1;
                  break;
              }
    }
    if(flag==0)
       printf("\nPrime");
    else
     printf("\n NOt Prime");
}

void main()
{
    int N;
    printf("Enter No to Check : ");
    scanf("%d",&N);
    
    ch_prime(N);
}

Now lets further optimize it .

Now think if a number can't divide by 2 then it must not be divided by any even number .
so you don't have to check at even number . it reduce your number of steps by half .
this is really great achievement .

Now its time to implement it .

Related Post :  test your programming skill P-2

C Code :

1. // check given no is prime or NOt
2. /*
3. main concept :
4. we have to check its divisibility from 2 to sqrt(N)
5. &&
6. if a number is not divisible by 2 than it is also not divisible by even numbers
7. */
8.  
9.  
10. #include<stdio.h>
11. #include<math.h>
12.  
13. void check_prime(int N)
14. {
15.       int i,sq,flag=0;
16.       sq=sqrt(N);
17.       if(N%2 != 0)  //if number is not divisible by 2
18.       {
19.           for(i=3;i<=sq;i=i+2) //then start from three & increment by 2 till sqrt(N)
20.           {                    // divide by above term to check it is prime
21.               if(N%i == 0)
22.                   {
23.                       flag=1;  //flag counter =1 conform it is not prime
24.                       break;
25.                   }
26.         }
27.     }
28.     else
29.        flag=1;
30.        
31.    if(flag==0)
32.     printf("\nPrime");
33.    else
34.      printf("\n NOt Prime");
35.      
36. }
37.  
38. void main()
39. {
40.     int N;
41.     printf("Enter No to Check : ");
42.     scanf("%d",&N);
43.    
44.     if(N==2)     // 1 & 2 is treated as special case
45.       printf("\nPrime Number");
46.     else if(N==1)
47.            printf("\nNot a Prime Number");
48.     else
49.      check_prime(N);
50. }
51. 
    

Can we further optimise it . yes we can .
similar to concept of even number now think if number is not divisible by 3 then also not divisible by multiple of three . similar concept is applicable for 5,7 and so on ..
but till Now I can't find efficient way to implement this
If you found please share with us .

Related Post :  test your programming skill P-2

thanks Have a Nice day !!!