Tuesday, 31 December 2013

PRIME NUMBER PROGRAM FOR LARGE NUMBERS WITH 6 EFFICIENCY METHOD HANDLED

 
From childhood, we learned about  prime number program. But still we are not efficiently programmed that one. 
Here are the some efficiency handled for prime number program.
This program is designed for finding the prime number of  one followed by ten digits.







#include<iostream>


#include<math.h>

using namespace std;

int main()

{

   bool flag=true;

   unsigned long  long int start=1000000000001ULL,end=1000000010000ULL,i,k,sqrt_num;

   for(i=start;i<=end;i=i+2)

   {

      flag=true;

      sqrt_num=(unsigned int)sqrt(i*2);

      for(k=3;k<=sqrt_num;k+=2)

      {

         if(i%k==0)

         {

            flag=false;

            break;

         }

      }

      if(flag)

      {

         cout<<"\n PRIME:"<<i<<"\n";

      }

   }

   return 0;
}



EFFICIENY HANDLED 1:
bool flag=true;
Use bool datatype instead of int. Because int takes more bytes than bool. This may be simple but saves some bytes.

EFFICIENY HANDLED 2:
sqrt_num=(unsigned int)sqrt(i*2);
There is a rule for prime number “If the number cannot be divisible  by below  the sqrt double that number then it is an prime number”.
So check up to the sqrt of double that number.

EFFICIENY HANDLED 3:
 unsigned 
use unsigned datatype. Because prime number cannot be negative. It saves the memory.

EFFICIENY HANDLED 4:
Iterate the loop starting with 3. Because expect 2 there wont be any even prime number. so no need to check whether number is divisible by 2.

EFFICIENY HANDLED 5:
  for(i=start;i<=end;i=i+2)
Don’t check the prime number for even numbers. Because other that 2, No even number is prime number.

EFFICIENY HANDLED 6:
  for(k=3;k<=sqrt(i*2);k+=2) // Don’t do this mistake
When you do like this then for every iteration it will call the sqrt function for checking the condition.
It will eat of much off the execution time.

In addition to that there are lot of efficiency can be handled. There is lots of algorithm for prime number such as Sieve of Eratosthenes and so on. This article is focuses only on the writing basic prime number program with efficiency.