Sieve of Eratosthen algorithm

Sieve of Eratosthen algorithm is used to find primes.
The following codes(modified) are from Algorithms in C++ and Core Java Volume I.



Code 1:

// Modified Sieve of Eratosthenes Algorithm
// Sieve of Eratosthenes Algorithm
// Finding prime numbers less than N
#include
#include

using namespace std;

const int N = 10000; 

int main()
{

 clock_t cstart = clock();
    int a[N];
    int i;
    for ( i = 2; i < N; ++i )
    {
        a[i] = 1;
    } 
    
    for( i = 2; i < N; ++i )
    {
        if ( a[i] ) 
        {
            for( int j = i; j*i < N; ++j )
            {
                a[i*j] = 0;
            } 
        }
    }

   clock_t cend = clock();
   double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;

    cout  << millis << " milliseconds\n";
    cout << sizeof(int) << endl;
    return 0;
}

Code 2: using bitset

#include
#include
#include

using namespace std;

const int N = 2000000; 

int main()
{

 clock_t cstart = clock();
    
    bitset b;
    int i;
    int count = 0;

    b.set(); // set all bits to 1
    
    for(int k = 2; k < N; ++k )
    {
        if ( b.test(k) ) 
        {
            int j = k;
            // for( int j = k; j*k < N; ++j )
            while ( j*k <= N)
             {
                b.reset(j*k); // set j*k bit to 0
                ++j;
            } 
        }
    }

   i =2;

   while ( i <= N)
   {
    if (b.test(i)) ++count;
    ++i;

   }

   clock_t cend = clock();
   double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;

    cout << count << "primes\n"  << millis << " milliseconds\n";
    return 0;
}

Code 3: using BitSet

import java.util.*;

/**

 * This program runs the Sieve of Erathostenes benchmark. It computes all primes up to 2,000,000.

 * @version 1.21 2004-08-03

 * @author Cay Horstmann

 */

public class Sieve

{

   public static void main(String[] s)

   {

      int n = 2000000;

      long start = System.currentTimeMillis();

      BitSet b = new BitSet(n + 1);

      int count = 0;

      int i;

      for (i = 2; i <= n; i++)

         b.set(i);

      i = 2;

      while (i * i <= n)

      {

         if (b.get(i))

         {

            count++;

            int k = 2 * i;

            while (k <= n)

            {

               b.clear(k);

               k += i;

            }

         }

         i++;

      }

      while (i <= n)

      {

         if (b.get(i)) count++;

         i++;

      }

      long end = System.currentTimeMillis();

      System.out.println(count + " primes");

      System.out.println((end - start) + " milliseconds");

   }

}