Computing π(x): An analytic method

This paper presents a class of algorithms for computing π(x), the number of primes ≤ x. For each b with 0 ≤ b ≤ 1 4 and each ε{lunate} > 0 there is an algorithm A(b,ε{lunate}) which computes π(x) using O(x ^{3 5}- 2b 5+ε{lunate}) bit operations and uses O(x^b+ε{lunate}) bits of storage. In particular one can compute π(x) using O(x ^{3 5+ε{lunate}}) bit operations and O(x^ε{lunate}) space, or using O(x ^{1 2+ε{lunate}}) bit operations and O(x ^{1 4}) space. These algorithms are based on numerical integration of certain integral transforms of the Riemann §-function. This technique can be generalized to evaluate many other arithmetic functions, including the functions π(x; k, l) counting the number of primes p ≡ l (mod k) with p ≤ x and the function M(x) which is the partial sum of the Möbius function μ(n) over all n≤ x.