The combinatorial algorithm for computing $\pi (x)$

Abstract

This paper describes recent advances in the combinatorial method for computing $\pi (x)$, the number of primes $\le x$. In particular, the memory usage has been reduced by a factor of $\log x$, and modifications for shared- and distributed-memory parallelism have been incorporated. The resulting method computes $\pi (x)$ with complexity $O(x^{2/3}{\log }^{-2}x)$ in time and $O(x^{1/3}{\log }^{2}x)$ in space. The algorithm has been implemented and used to compute $\pi (10^n)$ for $1\le n\le 26$ and $\pi (2^m)$ for $1\le m\le 86$. The mathematics presented here is consistent with and builds on that of previous authors.

12 pages

Cited by in corpus (1)

• Strengthening the Baillie-PSW primality test