Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Computing $\pi (x)$: the Meissel-Lehmer method
HTML articles powered by AMS MathViewer

by J. C. Lagarias, V. S. Miller and A. M. Odlyzko PDF
Math. Comp. 44 (1985), 537-560 Request permission


E. D. F. Meissel, a German astronomer, found in the 1870’s a method for computing individual values of $\pi (x)$, the counting function for the number of primes $\leqslant x$. His method was based on recurrences for partial sieving functions, and he used it to compute $\pi ({10^9})$. D. H. Lehmer simplified and extended Meissel’s method. We present further refinements of the Meissel-Lehmer method which incorporate some new sieving techniques. We give an asymptotic running time analysis of the resulting algorithm, showing that for every $\varepsilon > 0$ it computes $\pi (x)$ using at most $O({x^{2/3 + \varepsilon }})$ arithmetic operations and using at most $O({x^{1/3 + \varepsilon }})$ storage locations on a Random Access Machine (RAM) using words of length $[{\log _2}x] + 1$ bits. The algorithm can be further speeded up using parallel processors. We show that there is an algorithm which, when given M RAM parallel processors, computes $\pi (x)$ in time at most $O({M^{ - 1}}{x^{2/3 + \varepsilon }})$ using at most $O({x^{1/3 + \varepsilon }})$ storage locations on each parallel processor, provided $M \leqslant {x^{1/3}}$. A variant of the algorithm was implemented and used to compute $\pi (4 \times {10^{16}})$.
Similar Articles
Additional Information
  • © Copyright 1985 American Mathematical Society
  • Journal: Math. Comp. 44 (1985), 537-560
  • MSC: Primary 11Y35; Secondary 11-04, 11N05
  • DOI:
  • MathSciNet review: 777285