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

Dean Hirsch, Ido Kessler, Uri Mendlovic

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 r…