Faster enumeration of primes
2026-06-22 • Data Structures and Algorithms
Data Structures and AlgorithmsSymbolic Computation
AI summaryⓘ
The authors introduce new algorithms to find all prime numbers up to a number N more efficiently than the traditional sieve of Eratosthenes. Their fastest method runs faster by a factor related to the logarithm of N, although it is not fully proven yet. They also offer guaranteed accurate versions, one using randomness and another fully deterministic, which are a bit slower but still improved over previous methods. The improvements come from advanced math techniques involving fast polynomial calculations and concepts from error-correcting codes.
prime numberssieve of Eratosthenesalgorithm complexitybit operationspolynomial arithmeticfinite fieldserror-correcting codesLas Vegas algorithmdeterministic algorithmlogarithmic speedup
Authors
David Harvey
Abstract
We describe several new algorithms for finding all prime numbers up to a given bound $N$, achieving the first ever speedup by a positive power of $\log N$ over the ancient sieve of Eratosthenes. The fastest version, which is not fully rigorous, runs in \[ N (\log \log N)^{1+o(1)} \] bit operations when analysed in the multitape Turing model. This improves on the best existing algorithms due to Pritchard (1981), Atkin--Bernstein (2004) and Sergeev (2016) by a factor of almost $\log N$. We also present a rigorous randomised (Las Vegas) variant that is slower by a factor of $(\log \log N)^{1+o(1)}$, and a rigorous deterministic variant that is slower by a factor of $(\log N)^{1/2+o(1)}$. The new algorithms make heavy use of fast polynomial arithmetic over finite fields, and also involve ideas from the theory of error-correcting codes.