Mathematical Sciences Research Institute

Home » Analytic Number Theory Seminar: The sieve of Eratosthenes in less space

Seminar

Analytic Number Theory Seminar: The sieve of Eratosthenes in less space February 16, 2017 (02:00 PM PST - 03:00 PM PST)
Parent Program: Analytic Number Theory MSRI: Simons Auditorium
Speaker(s) Harald Helfgott (Georg-August-Universität zu Göttingen)
Description No Description
Video
We will show how to carry out a sieve of Erastosthenes up to $N$ in space $O(N^{1/3})$ and essentially linear time. This improves over the usual versions, which take space about $O(\sqrt{N})$ and essentially linear time.  The algorithm -- which, like the one in (Galway, 2000), is ultimately related to diophantine approximation -- can also be used to factorize integers $n$, and thus to give the values of arithmetical functions such as the M\"obius function $\mu$ and the Liouville function $\lambda$ for all integers up to $N$.