## 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

## Abstract:

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}})$.

## References

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592**
M. A. Auslander & M. E. Hopkins, "An overview of PL.8 compiler," - Jan Bohman,
*On the number of primes less than a given limit*, Nordisk Tidskr. Informationsbehandling (BIT)**12**(1972), 576–578. MR**321890**, DOI 10.1007/bf01932967
L. E. Dickson, - Richard H. Hudson and Alfred Brauer,
*On the exact number of primes in the arithmetic progressions $4n\pm 1$ and $6n\pm 1$*, J. Reine Angew. Math.**291**(1977), 23–29. MR**441892**, DOI 10.1515/crll.1977.291.23 - J. C. Lagarias and A. M. Odlyzko,
*New algorithms for computing $\pi (x)$*, Number theory (New York, 1982) Lecture Notes in Math., vol. 1052, Springer, Berlin, 1984, pp. 176–193. MR**750665**, DOI 10.1007/BFb0071543
J. C. Lagarias & A. M. Odlyzko, "Computing $\pi (x)$: An analytic method." (Preprint.)
E. Landau, - D. H. Lehmer,
*On the exact number of primes less than a given limit*, Illinois J. Math.**3**(1959), 381–388. MR**106883**, DOI 10.1215/ijm/1255455259 - David C. Mapes,
*Fast method for computing the number of primes less than a given limit*, Math. Comp.**17**(1963), 179–185. MR**158508**, DOI 10.1090/S0025-5718-1963-0158508-8 - Meissel,
*Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen*, Math. Ann.**2**(1870), no. 4, 636–642 (German). MR**1509683**, DOI 10.1007/BF01444045 - Meissel,
*Berechnung der Menge von Primzahlen. welche innerhalb der ersten Hundert Millionen natürlicher Zahlen vorkommen*, Math. Ann.**3**(1871), no. 4, 523–525 (German). MR**1509719**, DOI 10.1007/BF01442832
E. D. F. Meissel, "Über Primzahlmengen," - Meissel,
*Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde natürlicher Zahlen vorkommen*, Math. Ann.**25**(1885), no. 2, 251–257 (German). MR**1510308**, DOI 10.1007/BF01446409 - Herbert S. Wilf,
*What is an answer?*, Amer. Math. Monthly**89**(1982), no. 5, 289–292. MR**653502**, DOI 10.2307/2321713

*Proceeding of the SIGPLAN*82

*Symposium on Compiler Construction*, Boston, 1982.

*History of the Theory of Numbers*, Volume 1, Chapter XVIII, Chelsea, New York, 1971. (Reprint.)

*Primzahlen*, reprint, Chelsea, New York, 1958.

*Math. Ann.*, v. 21, 1883, p. 304.

## Additional Information

- © Copyright 1985 American Mathematical Society
- Journal: Math. Comp.
**44**(1985), 537-560 - MSC: Primary 11Y35; Secondary 11-04, 11N05
- DOI: https://doi.org/10.1090/S0025-5718-1985-0777285-5
- MathSciNet review: 777285