Computing \pi(N): An elementary approach in \tilde{O}(\sqrt{N}) time

arXiv2212.09857MaRDI QIDQ6421028FDOQ6421028

Authors: Dean Hirsch, Ido Kessler, Uri Mendlovic 

Publication date: 19 December 2022

Abstract: We present an efficient and elementary algorithm for computing the number of primes up to $N$ in $ildeO(sqrtN)$ time, improving upon the existing combinatorial methods that require $ildeO(N^{2/3})$ time. Our method has a similar time complexity to the analytical approach to prime counting, while avoiding complex analysis and the use of arbitrary precision complex numbers. While the most time-efficient version of our algorithm requires $ildeO(sqrtN)$ space, we present a continuous space-time trade-off, showing, e.g., how to reduce the space complexity to $ildeO(sqrt[3]N)$ while slightly increasing the time complexity to $ildeO(N^{8/15})$. We apply our techniques to improve the state-of-the-art complexity of elementary algorithms for computing other number-theoretic functions, such as the the Mertens function (in $ildeO(sqrtN)$ time compared to the known $ildeO(N^{0.6})$), summing Euler's totient function, counting square-free numbers and summing primes. Implementation code is provided.

Has companion code repository: https://github.com/primecounting/primecounting

This page was built for publication: Computing $\pi(N)$: An elementary approach in $\tilde{O}(\sqrt{N})$ time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421028)