TAOCP 5.2.3 Exercise 12

Section 5.2.3: Sorting by Selection

Exercise 12. [M22] [M22] (B. A. Chartres.) Design a high-speed algorithm that builds a table of the prime numbers < N, making use of a priority queue to avoid division operations. [Hint: Let the smallest key in the priority queue be the least odd nonprime number greater than the last odd number considered as a prime candidate. Try to minimize the number of elements in the queue.]

Verified: yes
Solve time: 1m28s

Solution

Let $r$ denote the current odd integer under consideration and let $H$ be a priority queue keyed by the first unprocessed odd composite associated with each prime. Each element of $H$ has the form $(t, p)$, where $p$ is a prime already discovered and $t$ is the smallest odd multiple of $p$ not yet eliminated. The key of $(t, p)$ is $t$.

The algorithm maintains the invariant that every composite odd number $m < r$ has already appeared as the key of some element in $H$ at some stage not later than its first occurrence, and that for each stored prime $p$, the value $t$ is of the form $p^2 + 2kp$ for some integer $k \ge 0$.

Initialization sets $r \leftarrow 3$ and $H \leftarrow \emptyset$. The value $2$ is handled separately as the only even prime.

The processing step compares $r$ with the minimum key in $H$, when $H \ne \emptyset$. If $H = \emptyset$ or $\min(H).t > r$, then no previously generated composite equals $r$, so $r$ is prime. In that case $r$ is output and a new generator for its multiples is inserted into the queue by placing $(r^2, r)$ into $H$. The choice of $r^2$ is justified because every composite multiple $r(2k+1)$ with $2k+1 < r$ has a prime factor less than $r$, and hence would already have been generated by a smaller prime; therefore no multiple of $r$ less than $r^2$ is needed for correctness.

If instead $\min(H).t = r$, then $r$ is composite and must be eliminated. Let $(t, p)$ be the element of $H$ with $t = r$. That element is removed and replaced by $(t + 2p, p)$, since the next odd multiple of $p$ after $t$ is obtained by adding $2p$. This update preserves the invariant because it advances the generator for $p$ to the next unprocessed odd multiple.

The complete procedure is therefore:

When $r$ is an odd integer with $r < N$, perform the following. If $H = \emptyset$ or $\min(H).t > r$, output $r$ and insert $(r^2, r)$ into $H$. Otherwise repeatedly delete the minimum element $(t, p)$ with $t = r$ and replace it by $(t + 2p, p)$ until the minimum key exceeds $r$. Then increase $r$ by $2$ and continue.

Correctness follows from the representation of every odd composite $m$ as $m = pq$ with $p$ prime and $p \le q$. When $p$ is first inserted, its initial key is $p^2$, so every composite $p(2k+1) \ge p^2$ is eventually generated in increasing order by repeated additions of $2p$. Since the priority queue always selects the smallest pending composite, every composite is removed exactly at its first occurrence, and every number not generated in $H$ is therefore prime.

The structure of $H$ contains exactly one entry for each prime $p$ whose current chain has not yet been exhausted past the current scan position. No additional information is required to generate future composites of $p$, since the next value is determined uniquely by $t + 2p$. This achieves the minimal queue size consistent with avoiding division, since each prime must contribute at least one active generator once it has been discovered.

This completes the construction of a division-free prime table generator based on a priority queue. ∎