HOW TO CHECK EFFICIENTLY IF A NUMBER IS PRIME OR NOT

A number is a prime number if that number has precisely two distinct divisors, one and itself. First ten prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

So, if we can find that N has two divisors than it’s a prime number else not, this is actually brute force approach and the complexity is O (N). How we do that, starting from 1 to N we have check if N is divisible by 1, 2, 3, ….., N each time it divide we increment our divisor count by one and at the end we will check if the divisor count is 2 or not.

Can we do better, yes we can. Look carefully the only even prime is 2. If we add an if condition that if the number is 2 return true else false if the number is even, because other even numbers can’t not be a prime number. For even numbers the complexity becomes O (1). So what about odd numbers? How can we improve that? We can reduce the complexity for odd number O (N / 2). See we don’t need to divide by even numbers because the Number N is an odd number, so it will never be divide by an even number. So we have to check if N is divisible by 1, 3, 5, 7, 9, 11, 13, 15 …. N.

We never satisfied! We need more yes the ultimate complexity of an odd number to check whether it’s prime or not is O (√N).
For finding if the number has any divisors other then 1 and itself it will appear under the square root of N, we don’t need to check up to N.


Java implementation of this method is,

public static boolean IsPrime(long num) {
        
      if(num < 2)
          return false;

     if(num == 2)
       	return true;

      if( (num & 1) == 0)  // the number is even    
          return false;
        
      long sqrt = (int) Math.sqrt(num); 
        
      for(int i = 3; i <= sqrt; i += 2) {
          if(num % i == 0)
             return false;
      }  
    return true;  
}

S. Mahbub – Uz – Zaman
Tuesday, September 13, 2011

Advertisements

4 thoughts on “HOW TO CHECK EFFICIENTLY IF A NUMBER IS PRIME OR NOT

  1. In addition to division upto the square root (ceil) of the integer, skipping integers multiples of 2’s and 3’s for division can be achieved easily.

    /*n is the upper limit*/
    int dx=4,i=5,n;
    while(i <=n)
     {
       printf("%d",i);
    /* Generates the the difference,   *
     * the alernating 2 and 4 sequence */
    
       dx=-(dx-6);
    
    /* Adds the generated difference 'dx' with   *
     * with the current value of 'i' to get the  *
     * next value of the series with no multiple *
     * of 2 and 3                                */
    
       i=i+dx;
     }
    

    This geneartes a series of integers which are not multiple of 2 or 3 or both. The integers of this series can be used to divide a given integer. Skipping the even integers saven 50% division and skipping multiple of 3s avoids an additional 17% divisions, that makes total 67% avoided integer divisions.

    Checkout: phoxis.org/2009/05/07/generating-twin-primes/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s