Wednesday 5 March 2014

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 :



// 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 :

Effective Way to test Number is Prime or Not .

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).

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 .

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%== 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. }


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 .
thanks Have a Nice day !!!

2 comments:

  1. What's up to all, for the reason that I am actually eager of
    reading this webpage's post to be updated regularly. It carries nice information.

    Feel free to surf to my homepage: Cheap Dr Dre Beats

    ReplyDelete
  2. Hello friends, how is all, and what you wish for
    to say on the topic of this paragraph, in my view
    its actually amazing for me.

    My site - Beats By Dr Dre

    ReplyDelete

THANKS FOR UR GREAT COMMENT

Blogger Widgets