Two fast parallel prime number sieves

DOI10.1006/INCO.1994.1082MaRDI QIDQ1336051zbMATH OpenOpenAlexFDO

Authors Ian Parberry, Jonathan P. Sorenson

Publication date 12 October 1994

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1994.1082

zbMATH Keywords

globally shared memory

Mathematics Subject Classification ID

Primality (11Y11) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Review text

The paper presents two parallel algorithms that list all prime numbers up to \(n\), a problem for which sequential algorithms of complexity \(O(n/ \log \log n)\) are known [\textit{H. G. Mairson}, Commun. ACM 20, 664-669 (1977; Zbl 0355.68040); \textit{P. Pritchard}, Comm. ACM 24, 18-23, 772 (1981; Zbl 0454.68084)]. In the `Exclusive Read, Exclusive Write' algebraic parallel random access model of computation, the first algorithm uses \(O(\log n)\) time and \(O(n/(\log n\log\log n))\) processors. It is based on a sequential algorithm of \textit{P. Pritchard} [Sci. Comput. Program. 9, 17-35 (1987; Zbl 0627.68033)]. The second algorithm uses \(O (\sqrt n)\) time and \(O (\sqrt n)\) processors, so it is theoretically less efficient. However, because of the absence of very fine-grained parallelism, it may be more efficient in practice. This observation is formalized by analyzing both algorithms in a model of parallel computation that allows for the communication latency inherent in a globally shared memory [\textit{A. Aggarwal}, \textit{A. K. Chandra}, \textit{M. Snir}, Annual ACM Symposium on parallel algorithms and architectures, 1, 11-21 (1989)].

Recommendations

• A space-efficient fast prime number sieve
• Fast compact prime number sieves (among others)
• Linear prime-number sieves: A family tree
• scientific article; zbMATH DE number 1186941
• Cache optimized sieve

Cited in

(13)

• Linear prime-number sieves: A family tree
• Prime numbers as a tool to design distributed algorithms
• The I/O complexity of computing prime tables
• Statistical Evidence for Small Generating Sets
• scientific article; zbMATH DE number 5670033 (Why is no real title available?)
• Modular exponentiation via the explicit Chinese remainder theorem
• Two compact incremental prime sieves
• Simple parallel algorithms for primality testing and integer factorization
• scientific article; zbMATH DE number 1014825 (Why is no real title available?)
• An improved sieve of Eratosthenes
• Parallel implementations of Brunotte's algorithm
• A space-efficient fast prime number sieve
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM

This page was built for publication: Two fast parallel prime number sieves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336051)