Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Computing $\pi(x)$: the Meissel, Lehmer, Lagarias,
Miller, Odlyzko method


Authors: M. Deleglise and J. Rivat
Journal: Math. Comp. 65 (1996), 235-245
MSC (1991): Primary 11N05, 11Y70
DOI: https://doi.org/10.1090/S0025-5718-96-00674-6
MathSciNet review: 1322888
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\pi(x)$ denote the number of primes $\le x$. Our aim in this paper is to present some refinements of a combinatorial method for computing single values of $\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 $\pi(x)$ in $O(\frac{x^{2/3}} {\log^2x})$ time and $O(x^{1/3}\log^3x\log \log x)$ space. The algorithm has been implemented and used to compute $\pi(10^{18})$.


References [Enhancements On Off] (What's this?)

  • 1 J. Bohman, On the number of primes less than a given limit, BIT 12 (1972), 576--578. MR 48:255
  • 2 J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi(x)$: The Meissel-Lehmer method, Math. Comp. 44 (1985), 537--560. MR 86h:11111
  • 3 J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: An analytic method, J. Algorithms 8 (1987), 173--191. MR 88k:11095
  • 4 E. D. F. Meissel, Über die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen, Math. Ann. 2 (1870), 636--642.
  • 5 ------, Berechnung der Menge von Primzahlen, welche innerhalb der ersten hundert Millionen natürlicher Zahlen vorkommen, Math. Ann. 3 (1871), 523--525.
  • 6 ------, Über Primzahlenmengen, Math. Ann. 21 (1883), 304.
  • 7 ------, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde natürlicher Zahlen vorkommen, Math. Ann. 25 (1885), 289--292.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11N05, 11Y70

Retrieve articles in all journals with MSC (1991): 11N05, 11Y70


Additional Information

M. Deleglise
Affiliation: Département de Mathématiques, Université Lyon 1, 43 Blvd. du 11 Novembre 1918, 69622 Villeurbanne Cedex, France
Email: deleglis@lmdi.univ-lyon1.fr

J. Rivat
Affiliation: Département de Mathématiques, Université Lyon 1, 43 Blvd. du 11 Novembre 1918, 69622 Villeurbanne Cedex, France
Email: rivat@caissa.univ-lyon1.fr

DOI: https://doi.org/10.1090/S0025-5718-96-00674-6
Received by editor(s): January 12, 1994
Received by editor(s) in revised form: December 1, 1994
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society