Two fast parallel prime number sieves (Q1336051)

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)].