Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm that finds all the primes in $2,3,\dots ,n$ in $\mathcal{O}(n\log (\log (n)))$ time and $\mathcal{O}(n)$ space.

Hint

This problem can also be solved by Euler’s Sieve in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

Algorithm

Lemma

$$\forall m\in {\mathbb{Z}}_{+}\setminus \{1\},m\in \mathbb{P}\iff \forall p\in \{p:p\in \mathbb{P}\wedge p<m\},p\nmid m$$

For $m=2,3,\dots ,n$, if $m$ is not marked, mark all the multiples of $m$ greater than $m$. Applying the lemma yields that $m$ is prime iff $m$ is unmarked.

This algorithm solves the problem in $\mathcal{O}(n\log (\log (n)))$ time and $\mathcal{O}(n)$ space.

std::vector f(n + 1, true);
std::vector<int> primes;
 
for (int i = 2; i <= n; i++) {
	if (f[i]) {
		primes.push_back(i);
		for (int j = 2 * i; j <= n; j += i) {
			f[j] = false;
		}
	}
}
 
return primes;

Proof

Let $p_i$ be the $i$-th smallest prime, then

$$\begin{array}{rl}T(n)& \in \mathcal{O}\left(\sum _{i=1}^{\pi (n)}\frac{n}{p_i}\right)\\ & =\mathcal{O}\left(n\sum _{i=2}^{\pi (n)}\frac{1}{i\log (i)}\right)\\ & =\mathcal{O}\left(n{\int }_2^{\pi (n)}\frac{\mathrm{d}x}{x\log (x)}\right)\\ & =\mathcal{O}(n\log (\log (n)))\end{array}$$