Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method
M. Deleglise, J. Rivat
Source record
Source: Crossref
Published: Jan 1, 1996
DOI: 10.1090/s0025-5718-96-00674-6
Open original source ↗Source abstract
Let π ( x ) \pi (x) denote the number of primes ≤ x \le x . Our aim in this paper is to present some refinements of a combinatorial method for computing single values of π ( x ) \pi (x) , initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute π ( x ) \pi (x) in O ( x 2 / 3 log 2 x ) O(\frac {x^{2/3}} {\log ^2x}) time and O ( x 1 / 3 log 3 x log log x ) O(x^{1/3}\log ^3x\log \log x) space. The algorithm has been implemented and used to compute π ( 10 18 ) \pi (10^{18}) .
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.