Euler's Sieve

Euler’s Sieve is an algorithm that finds all the primes in $2,3,\dots ,n$ in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

Hint

This problem can also be solved by the Sieve of Eratosthenes in $\mathcal{O}(n\log (\log (n)))$ time and $\mathcal{O}(n)$ space.

Algorithm

Lemma

$$\forall m\in {\mathbb{Z}}_{+}\setminus \{1\},m\in \mathbb{P}\iff \mathrm{lpf}(m)=m$$

For $m=2,3,\dots ,n$, mark all $k$ such that $\frac{k}{\mathrm{lpf}(k)}=m$. Applying the lemma yields that $m$ is prime iff $m$ is unmarked.

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 : primes) {
		if (i * j > n) {
			break;
		}
		f[i * j] = false;
		if (i % j == 0) {
			break;
		}
	}
}
 
return primes;

Proof

It is easy to prove that each integer is marked at most once.