Linear prime-number sieves: A family tree (Q1092658)

The idea of a ``sieve'' to list prime numbers up to a limit N dates back to Eratosthenes. The process is a sieve in the sense that the primes are obtained indirectly by ``shifting out'' the composite numbers in the interval \(2\leq n\leq N\). The set of composite numbers can be partitioned into subset \(C_ k\) whose members have \(p_ k\) as their smallest prime divisor. In the implementation of such a sieve one needs to compute \(C_ k\) and then to locate \(p_{k+1}\). In 1981 the author [Commun. ACM 24, 18-23 (1981; Zbl 0454.68084); see also \textit{J. Misra}, ACM Trans. Program. Lang. Syst. 3, 104-109 (1981; Zbl 0454.68004)] introduced a novel way to remove these composite numbers by generating them in decreasing order. Here the author shows that many prime listing algorithms are based on how the set of composite numbers is being partitioned; for example, \(C_ k\) can be the set of composite numbers with \(p_ k\) as their largest divisor instead. It is then emphasized that new and perhaps better algorithms can emerge from the transformation of abstract algorithms as well as from the variation of the time-order of operations.