Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An improved sieve of Eratosthenes

Author: Harald Andrés Helfgott
Journal: Math. Comp. 89 (2020), 333-350
MSC (2010): Primary 11Y05, 11Y16; Secondary 11Y11
Published electronically: April 23, 2019
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11Y16, 11Y11

Retrieve articles in all journals with MSC (2010): 11Y05, 11Y16, 11Y11

Additional Information

Harald Andrés Helfgott
Affiliation: Mathematisches Institut, Georg-August Universität Göttingen, Bunsenstraße 3-5, D-37073 Göttingen, Germany; and IMJ-PRG, UMR 7586, 58 avenue de France, Bâtiment S. Germain, case 7012, 75013 Paris CEDEX 13, France

Received by editor(s): April 25, 2018
Received by editor(s) in revised form: December 3, 2018, and February 22, 2019
Published electronically: April 23, 2019
Additional Notes: The author was supported by funds from his Humboldt Professorship.
Article copyright: © Copyright 2019 American Mathematical Society