The combinatorial algorithm for computing pi(x)

Abstract

This thesis describes recent advances in the combinatorial method for computing pi(x), the number of primes less-than or equal-to 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 x)^(-2)) in time and O(x^(1/3) (log x)^2) in space. The algorithm has been implemented and used to compute pi(10^n) for 1 <= n <= 26 and pi(2^m) for 1 <= m <= 86. The mathematics presented here is consistent with and builds on that of previous authors.