Two Compact Incremental Prime Sieves

<p> A prime sieve is an algorithm that finds the primes up to a bound <em> n </em> . We say that a prime sieve is <em> incremental </em> , if it can quickly determine if <em> n </em> +1 is prime after having found all primes up to <em> n </em> . We say a sieve is compact if it uses roughly &radic; <em> n </em> space or less. In this paper, we present two new results. <ul> <li> We describe the <em> rolling sieve </em> , a practical, incremental prime sieve that takes <em> O </em> ( <em> n </em> log log <em> n </em> ) time and <em> O </em> (&radic; <em> n </em> log <em> n </em> ) bits of space. </li> </ul> <ul> <li> We also show how to modify the sieve of Atkin and Bernstein from 2004 to obtain a sieve that is simultaneously sublinear, compact, and incremental. </li> </ul></p><p> The second result solves an open problem given by Paul Pritchard in 1994.</p>