Benchmarking various prime number generator algorithms

Objective : Finding primes in the rage 1 <= x <= 1,000,000,000

This comparison is done in a 8GB, 2.5 GHz Intel i5 machine. C++ version 4.1.2

Method 1: Naive algorithm

 bool sieve[1000000001];  
 bool checkPrime(long N){  
  if(N < 2){  
  return false;  
  }  
  for(long i=2;i<= sqrt(N);i++){  
  if((N % i) == 0 ){  
   return false;  
  }  
  }  
  return true;  
 }  
 void populateNaive(long N){  
  for(long i=0;i<N;i++){  
  sieve[i] = checkPrime(i);  
  }  
 } 

Time Taken : waited for 6 hours, closed it.

Method 2: Sieve of Eratosthenes

 bool sieve[1000000001];  
 void populateSieveE(long N){  
  sieve[1] = true; // true means a not prime  
  for(long i = 1;i<N;i++){  
  if(!sieve[i]){  
   for(long j = i+i ; j< N; j+=i){ //marking multiples of prime as not prime  
   sieve[j] = true;  
   }  
  }  
  }  
 }  

Time Taken : 38.2064 seconds.

Method 3: Optimised Sieve of Eratosthenes
Idea is to avoid multiples of 2 

 bool sieve[1000000001];  
 void populateSieveErastosthenesOptimised(long N){  
  sieve[1] = true; // true means a not prime  
  for(long i = 4;i<N;i+=2){ //treating two as a special case  
  sieve[i] = true;  
  }  
  for(long i = 1;i<N;i++){  
  if(!sieve[i]){  
   long offset = 2 * i; // traverse only through odd multiples  
   for(long j = offset+i ; j< N; j += offset){  
   sieve[j] = true;  
   }  
  }  
  }  
 }  

Time Taken : 24.8205 seconds.

Method 3: Further optimised Sieve of Eratosthenes
The only change from method 2 is to traverse only upto sqrt(N)

 bool sieve[1000000001];  
 void populateSieveErastoSthenesOptimised(long N){  
  sieve[1] = true; // true means a not prime  
  for(long i = 4;i<N;i+=2){ //treating two as a special case  
  sieve[i] = true;  
  }  
  for(long i = 1;i<= sqrt(N);i++){ // the only change is to traverse only upto sqrt(N)  
  if(!sieve[i]){  
   long offset = 2 * i; // traverse only through odd multiples  
   for(long j = offset+i ; j< N; j += offset){  
   sieve[j] = true;  
   }  
  }  
  }  
 }  

Time Taken : 13.602 seconds

Method 4: Sieve of Atkins

 bool sieve[1000000001];  
 void sieveOfAtkin(long n){  
  sieve[2] = true;  
  sieve[3] = true;  
  long lim = ceil(sqrt(n));  
  for (long x = 1; x <= lim; x++)  
   {  
     for (long y = 1; y <= lim; y++)  
     {  
       long num = (4 * x * x + y * y);  
       if (num <= n && (num % 12 == 1 || num % 12 == 5))  
       {  
         sieve[num] = true;  
       }  
       num = (3 * x * x + y * y);  
       if (num <= n && (num % 12 == 7))  
       {  
         sieve[num] = true;  
       }  
       if (x > y)  
       {  
         num = (3 * x * x - y * y);  
         if (num <= n && (num % 12 == 11))  
         {  
           sieve[num] = true;  
         }  
       }  
     }  
   }  
   for (long i = 5; i <= lim; i++)  
   {  
     if (sieve[i])  
     {  
       for (long j = i * i; j <= n; j += i)  
       {  
         sieve[j] = false;  
       }  
     }  
   }  
 }  

Time Taken : 45.8392 seconds

This was very surprising, as I expected a better run time for Sieve of Atkins compared to other methods. On research found that the basic algorithm mentioned in Wikipedia is not optimised and  Sieve of Atkins high performance can be achieved only through proper optimisations. Found this link very informative as well http://stackoverflow.com/questions/19388106/the-sieve-of-atkin

How to initialise a boolean array in C++ with false

C++ version = 4.2.1

 #include<iostream>  
 using namespace std;  
 bool arr0[10];  
 int main(){  
  bool arr1[10] = {false};  
  bool arr2[10] = {0};  
  bool arr3[10];  
  for(int i=0;i<10;i++){  
  cout<<arr0[i]<<" ";  
  }  
  cout<<"\n";  
  for(int i=0;i<10;i++){  
  cout<<arr1[i]<<" ";  
  }  
  cout<<"\n";  
  for(int i=0;i<10;i++){  
  cout<<arr2[i]<<" ";  
  }  
  cout<<"\n";  
  for(int i=0;i<10;i++){  
  cout<<arr3[i]<<" ";  
  }  
  return 0;  
 }  

Output :

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 

So the output is self explanatory. Irrespective of the various methods used, a boolean array is always getting initialised with false.