Algorithms for PSSPS  The Pseudosquares Prime Sieve
Jon Sorenson Butler University
Monday, May 23, 2005 2:30 p.m., 2310 CS (Cookies: 2310 CS)
A prime number sieve is an algorithm that finds all primes up to a bound n. I will present a new sieve, based on the pseudosquares prime test of Lukes, Patterson, and Williams, that is conjectured to find all primes up to n in O( n log n) arithmetic operations using O( (log n)^2 ) space. Although the complexity of the algorithm is based on unproven conjectures, the correctness of the output is unconditional. Using this algorithm, we found the primes between 10^32 and 10^32+10^6 in about 3 minutes on a 1.0 GHz Pentium IV running Linux. The best previous prime sieve, due to Atkins and Bernstein, takes only O( n / loglog n ) operations but requires n^{1/3+epsilon} space using a technique due to Galway.
