Computing π(x): An analytic method

J. C. Lagarias, A. M. Odlyzko

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

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(xb+ε{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.

Original languageEnglish (US)
Pages (from-to)173-191
Number of pages19
JournalJournal of Algorithms
Volume8
Issue number2
DOIs
StatePublished - Jun 1987

Fingerprint Dive into the research topics of 'Computing π(x): An analytic method'. Together they form a unique fingerprint.

  • Cite this