Id: arxiv/2606.22851 Url: https://arxiv.org/abs/2606.22851 Tags: math.NT, cs.DS, cs.SC Score: 0 Title: Faster enumeration of primes Domain: math.NT Source: arxiv Authors: David Harvey Reviews: 0 Subject: math.NT Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-22 Page: https://delphi.science/r/arxiv/2606.22851 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…