# Sieve of Eratosthenes – Generating Primes

# Problem

Given an integer N, generate all primes less than or equal to N.

# Sieve of Eratosthenes – Explanation

Sieve of Eratosthenes is an algorithm that generates all prime up to N. Read this article written by Jane Alam Jan on Generating Primes – LightOJ Tutorial. The pdf contains almost all the optimizations of the Sieve of Eratosthenes.

# Code

vector<int> prime; /Stores generated primes/ char sieve[SIZE]; /0 means prime/ void primeSieve ( int n ) { sieve[0] = sieve[1] = 1; /0 and 1 are not prime/ prime.push_back(2); /Only Even Prime/ for ( int i = 4; i <= n; i += 2 ) sieve[i] = 1; /Remove multiples of 2/ int sqrtn = sqrt ( n ); for ( int i = 3; i <= sqrtn; i += 2 ) { if ( sieve[i] == 0 ) { for ( int j = i * i; j <= n; j += 2 * i ) sieve[j] = 1; } } for ( int i = 3; i <= n; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i); }

Some lines from the code above can be omitted depending on the situation. But as a whole, the above code gives us two products, a `vector<int> prime`

which contains all generated primes and a `char[]`

sieve that indicates whether a particular value is prime or not. We will need sieve array for optimizations in other algorithms.

# Complexity

The algorithm has a runtime complexity of $O(N log (logN ) )$