The combinatorial algorithm for computing pi(x)
Date
2015
Authors
Staple, Douglas
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
prime counting function, pi(x)