  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/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/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.
