Explore the English language on a new scale using AI-powered English language navigator.

Sieve of Eratosthenes

Sieve of Eratosthenes is used to find prime numbers up to some predefined integer n. For sure, we can just test all the numbers in range from 2 to n for primality using some approach, but it is quite inefficient. Sieve of Eratosthenes is a simple algorithm to find prime numbers. Though, there are better algorithms exist today, sieve of Eratosthenes is a great example of the sieve approach.

Algorithm

First of all algorithm requires a bit array isComposite to store n - 1 numbers: isComposite[2 .. n]. Initially the array contains zeros in all cells. During algorithm's work, numbers, which can be represented as k * p, where k ≥ 2, p is prime, are marked as composite numbers by writing 1 in a corresponding cell. Algorithm consists of two nested loops: outer, seeking for unmarked numbers (primes), and inner, marking primes' multiples as composites.

For all numbers m: 2 .. n, if m is unmarked:
- add m to primes list;
- mark all it's multiples, lesser or equal, than n (k * m ≤ n, k ≥ 2);
otherwise, if m is marked, then it is a composite number.

Modification

Let's notice, that algorithm can start marking multiples beginning from square of a found unmarked number. Indeed,

For m = 2, algorithm marks

	2 * 2   3 * 2   4 * 2   5 * 2   6 * 2   7 * 2   ...

For m = 3,

	2 * 3

were already marked on m = 2 step.

For m = 5,

	2 * 5   3 * 5   4 * 5 (= 10 * 2)

were already marked on m = 2 and m = 3 steps.

Strong proof is omitted, but you can easily prove it on your own. Modified algorithm is as following:

For all numbers m: 2 .. √n, if m is unmarked:
- add m to primes list;
- mark all it's multiples, starting from square, lesser or equal than n (k * m ≤ n, k ≥ m);
otherwise, if m is marked, then it is a composite number;
check all numbers in range √n .. n. All found unmarked numbers are primes, add them to list.

Example

Apply sieve of Eratosthenes to find all primes in range 2..100.

Initial grid

Sieve of Eratosthenes example, initial grid

2 is prime, mark all multiples of 2, starting from 4

Sieve of Eratosthenes example, 2 is prime, mark all multiples of 2

3 is prime, mark all multiples of 3, starting from 9

Sieve of Eratosthenes example, 3 is prime, mark all multiples of 3, starting from 9

5 is prime, mark all multiples of 5, starting from 25

Sieve of Eratosthenes example, 5 is prime, mark all multiples of 5, starting from 25

7 is prime, mark all multiples of 7, starting from 49

Sieve of Eratosthenes example, 7 is prime, mark all multiples of 7, starting from 49

11² is more, than 100, all unmarked numbers are primes

Sieve of Eratosthenes example, 11^2 is more, than 100, all unmarked numbers are primes

Final result

Sieve of Eratosthenes example, final result

Complexity analysis

Computational complexity of the algorithm is O(nlog(log(n))). Strong proof of this fact is not too complex and based on several approximations from the prime numbers' theory. It can be found in [1]. The space complexity is O(n). Actually, on the modern hardware, algorithm will run out of memory much faster, than it would run out of time.

Code snippets

Java implementation

public void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

boolean[] isComposite = new boolean[upperBound + 1];

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

System.out.print(m + " ");

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)

if (!isComposite[m])

System.out.print(m + " ");

}

C++ implementation

void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int)sqrt((double)upperBound);

bool *isComposite = new bool[upperBound + 1];

memset(isComposite, 0, sizeof(bool) * (upperBound + 1));

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

cout << m << " ";

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)