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

We present an efficient and elementary algorithm for computing the number of primes up to $N$ in $\tilde{O}(\sqrt{N})$ time, improving upon the existing combinatorial methods that require $\tilde{O}(N^{2\mathrm{/}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 $\tilde{O}(\sqrt{N})$ space, we present a continuous space-time trade-off, showing, e.g., how to reduce the space complexity to $\tilde{O}(\sqrt[3]{N})$ while slightly increasing the time complexity to $\tilde{O}(N^{8\mathrm{/}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 $\tilde{O}(\sqrt{N})$ time compared to the known $\tilde{O}(N^{0.6})$), summing Euler’s totient function, counting square-free numbers and summing primes. Implementation code is provided.