# 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);**

- add
- 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);**

- add
- 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

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

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

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

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

### 11^{2} is more, than 100, all unmarked numbers are primes

### 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++)

if (!isComposite[m])

cout << m << " ";

delete [] isComposite;

}

## Recommended books

- Victor Shoup.
**A Computational Introduction to Number Theory and Algebra.** - Peter J. Giblin.
**Primes and Programming.** - David M. Bressoud.
**Factorization and Primality Testing.** - Hans Riesel.
**Prime Numbers and Computer Methods for Factorization.**

## Visualizers

## Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.

Every dollar helps!