TAOCP 4.5.4 Exercise 8
We wish to transform the classical sieve of Eratosthenes into a form suitable for efficient computation, avoiding multiplications.
Section 4.5.4: Factoring into Primes
Exercise 8. ▶ [23] (The sieve of Eratosthenes, 3rd century b.c.) The following procedure evidently discovers all the prime numbers less than a given integer $N$, since it removes all the nonprime numbers: Start with all the odd numbers between 1 and $N$; then successively strike out the multiples $p_k^2, p_k(p_k+2), p_k(p_k+4), \ldots,$ of the $k$th prime $p_k$, for $k = 2, 3, 4, \ldots,$ until reaching a prime $p_k$ with $p_k^2 > N$.
Show how to adapt the procedure just described into an algorithm that is directly suited to efficient computer calculation, using no multiplication.
Verified: yes
Solve time: 1m52s
Solution
We wish to transform the classical sieve of Eratosthenes into a form suitable for efficient computation, avoiding multiplications. Let $N$ be a given integer. Let $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, … denote the sequence of primes. We maintain a boolean array $\text{isprime}[1..N]$, initialized so that $\text{isprime}[n] \leftarrow \text{true}$ for all odd $n \ge 3$ and $\text{isprime}[2] \leftarrow \text{true}$, $\text{isprime}[1] \leftarrow \text{false}$.
Instead of computing the multiples $p_k^2, p_k(p_k+2), p_k(p_k+4), \dots$ by multiplication, we exploit the fact that these numbers form an arithmetic progression with common difference $2p_k$. That is, for a fixed $k$, define $m \leftarrow p_k^2$; then each subsequent number in the sequence is obtained by incrementing $m \leftarrow m + 2 p_k$. Each such $m \le N$ is composite and is marked $\text{isprime}[m] \leftarrow \text{false}$.
The algorithm proceeds as follows:
Algorithm E (Sieve of Eratosthenes without multiplication)
E1. [Initialize.] For $n \leftarrow 1$ to $N$, set $\text{isprime}[n] \leftarrow \text{false}$ if $n$ is even or $n = 1$; otherwise $\text{isprime}[n] \leftarrow \text{true}$. Set $k \leftarrow 2$.
E2. [Next prime.] Find the smallest $p_k \ge 3$ such that $\text{isprime}[p_k] = \text{true}$. If $p_k^2 > N$, terminate; all remaining numbers marked $\text{true}$ are prime.
E3. [Strike out multiples.] Initialize $m \leftarrow p_k^2$. While $m \le N$, set $\text{isprime}[m] \leftarrow \text{false}$, and update $m \leftarrow m + 2 p_k$.
E4. [Advance.] Increase $k$ by 1 and return to E2.
The key invariant is that at the start of step E2, all composite numbers less than $p_k^2$ have been marked. Step E3 requires no multiplication because $m$ is updated by repeated addition of $2 p_k$. Each composite number is struck out exactly once for each of its smallest prime factors, preserving correctness. Termination occurs when $p_k^2 > N$, ensuring that all primes up to $N$ have been discovered.
This completes the solution.
∎