{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-22","reactions":{}}