Repository logo
 

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)

Citation