sieve_of_Eratosthenes.cpp

/*
 * Sieve of Eratosthenes is an algorithm to find the primes 
 * that is between 2 to N (as defined in main).
 *
 * Time Complexity  : O(N)
 * Space Complexity : O(N)
 */

#include <iostream>
using namespace std;

#define MAX 10000000

int primes[MAX];

/*
 * This is the function that finds the primes and eliminates 
 * the multiples.
 */
void sieve(int N)
{
  primes[0] = 1;
  primes[1] = 1;
  for (int i = 2; i <= N; i++)
  {
    if (primes[i] == 1)
      continue;
    for (int j = i + i; j <= N; j += i)
      primes[j] = 1;
  }
}

/*
 * This function prints out the primes to STDOUT
 */
void print(int N)
{
  for (int i = 0; i <= N; i++)
    if (primes[i] == 0)
      cout << i << ' ';
  cout << '\n';
}

/*
 * NOTE: This function is important for the 
 * initialization of the array.
 */
void init()
{
  for (int i = 0; i < MAX; i++)
    primes[i] = 0;
}

int main()
{
  int N = 100;
  init();
  sieve(N);
  print(N);
}