Programming: Fastest Algorithm to Check Whether Given Number is Prime or not

Hello to one and all..

I am going to discuss some methods to check whether given number is prime or not. But before we go any further, notice that the reason we use different methods here is to check whether method being used, decreases the time complexity or not. So here we go.

It is required to write a function that takes an integer and returns true if that integer is prime else it returns false.
well, a number is prime if and only if it has exactly two distinct natural number divisors: 1 and itself.
So for example 2, 3, 5, 7, 11, … , 97 , … are all prime, while 24 is not prime because it is divisible by 2,3,4,6,7 and 8. To find if a number n is prime we could simply (using brute force attack) check if it divides any numbers below it. We can use the modulus (%) operator to check for divisibility:

Method 1:

bool IsPrime(int num)
{
 if(num<=1)
  return false;
 for(int i=2; i<num; i++)
 {
  if(num%i==0)
   return false;
 }
 return true;
}

We can optimize this function by noticing that we only need to check divisibility for values of i that are less or equal to the square root of num. And if we couldn’t find a divisor under the square root it is impossible mathematically to find another one above the square root because divisors of any number come in couples, the multiplication of any two couples will be the original number. 

For example 64 has the following divisors:
1           64
2           32
4            16
8           (8)

note here is a special case because 64 has a perfect square root (8) so, while checking the divisors we have to check up to the square root itself. 

Method 2 (Improvement of Method 1) : 

bool IsPrime(int num) 
{ 
 if(num<=1) 
       return false; 
 for(int i=2; i<=sqrt(num*1.0); i++) 
 { 
        if(num%i==0) 
        return false; 
 } 
 return true; 
}

sqrt() function needs you to include “cmath” file and it takes one double parameter so I multiply our int by 1.0

Another optimization is to realize that there are no even primes greater than 2. Once we’ve checked that n is not even we can safely increment the value of i by 2. We can now write the final method for checking whether a number is prime: 

Method 3 (Improvement in Previous Methods) :- 

bool IsPrime(int num) 
{ 
 if(num<=1) 
         return false; 
 if(num==2) 
          return true; 
 if(num%2==0) 
         return false; 
 int sRoot = sqrt(num*1.0); 
 for(int i=3; i<=sRoot; i+=2) 
 { 
        if(num%i==0) 
        return false; 
 } 
 return true; 
}

the check in line 5 returns true if the number is 2 because we returns false for all even numbers after it.

I used the following project to test the time needed to check if the numbers from 0 to 100000 are prime or not:


#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;

bool IsPrime(int num)
{
 //past one of the previos versions
}

void main()
{
 clock_t start,end;
 start=clock();
 for(int i=0; i<=100000; i++)
  IsPrime(i);
 end=clock();
 cout<<"Version 1 takes "<<end-start<<" msec"<<endl;

}

And I got:










So the final method will decrease the time complexity from 7328 msec to 47 msec.

Its really great. This article has been shared from Holmezideas. Hope you find it helpful. .......More....Next Time.... :p