2 FAST PARALLEL PRIME NUMBER SIEVES

A prime number sieve is an algorithm that lists all prime numbers up t o a given bound n. Two parallel prime number sieves for an algebraic E REW PRAM model of computation are presented and analyzed. The first si eve runs in O(log n) time using O(n/(log n log log n)) processors, and the second sieve runs in O(root n) time using O(root n) processors. T he first sieve is optimal in the sense that it performs work O(n/log l og n), which is within a constant factor of the number of arithmetic o perations used by the fastest known sequential prime number sieves. Ho wever, when both sieves are analyzed on the Block PRAM model as define d by Aggarwal, Chandra, and Snir, it is found that the second sieve is more work-efficient when communication latency is significant. (C) 19 94 Academic Press, Inc.