An improved sieve of Eratosthenes
From MaRDI portal
Publication:5235102
DOI10.1090/MCOM/3438zbMATH Open1450.11122arXiv1712.09130OpenAlexW2962847573WikidataQ128231791 ScholiaQ128231791MaRDI QIDQ5235102
Author name not available (Why is that?)
Publication date: 7 October 2019
Published in: (Search for Journal in Brave)
Abstract: We show how to carry out a sieve of Eratosthenes up to N in space O(N^{1/3} (log N)^{2/3}) and time O(N log N). These bounds constitute an improvement over the usual versions of the sieve, which take space about O(sqrt{N}) and time at least linear on N. We can also apply our sieve to any subinterval of [1,N] of length Omega(N^{1/3} (log N)^{2/3}) in time essentially linear on the length of the interval. Before, such a thing was possible only for subintervals of [1,N] of length Omega(sqrt{N}). Just as in (Galway, 2000), our approach is related to Diophantine approximation, and also has close ties to Voronoi'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.
Full work available at URL: https://arxiv.org/abs/1712.09130
No records found.
No records found.
This page was built for publication: An improved sieve of Eratosthenes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5235102)
