An improved sieve of Eratosthenes

Abstract:

We show how to carry out a sieve of Eratosthenes up to $N$ in space $O\left (N^{1/3} (\log N)^{2/3}\right )$ and time $O(N \log N)$. In comparison, the usual versions of the sieve take space about $O(\sqrt {N})$ and time at least linear on $N$. We can also apply our sieve to any subinterval of $\lbrack 1,N\rbrack$ of length $\Omega \left (N^{1/3}\right )$ in time close to linear on the length of the interval. Before, such a thing was possible only for subintervals of $\lbrack 1,N\rbrack$ of length $\Omega (\sqrt {N})$.

Just as in (Galway, 2000), the approach here is related to Diophantine approximation, and also has close ties to Voronoï’s work on the Dirichlet divisor problem. The advantage of the method here resides in the fact that, because the method we will give is based on the sieve of Eratosthenes, we will also be able to use it to factor integers, and not just to produce lists of consecutive primes.