Linear prime-number sieves: A family tree
type: Item
instance of: scholarly article
title: Linear prime-number sieves: A family tree
zbMATH Open document ID: 0627.68033
DOI: 10.1016/0167-6423(87)90024-4
published in: Science of Computer Programming
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 11N35
zbMATH DE Number: 4020470
zbMATH Keywords: prime-number sieves
zbMATH Keywords: prime listing algorithms
author: Paul A. Pritchard
reviewed by: Peter Shiu
MaRDI profile type: Publication
full work available at URL: 0167-6423(87)90024-4
OpenAlex ID: W1997209544
description: scientific article; zbMATH DE number 4020470