Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
MathSciNet review: 1322888
Full-text PDF Free Access

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?)


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: http://dx.doi.org/10.1090/S0025-5718-96-00674-6
PII: S 0025-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