Meissel's Formula

A modification of Legendre's formula for the prime counting function pi(x). It starts with


where |_x_| is the floor function, P_2(x,a) is the number of integers p_ip_j<=x with a+1<=i<=j, and P_3(x,a) is the number of integers p_ip_jp_k<=x with a+1<=i<=j<=k, and so on.

Identities satisfied by the P_is include


for p_a<p_i<=sqrt(x) and


Meissel's formula is




Taking the derivation one step further yields Lehmer's formula.

See also

Legendre's Formula, Lehmer's Formula, Prime Counting Function

Explore with Wolfram|Alpha


Gram, J. "Rapport sur quelques calculs entrepris par M. Bertelsen et concernant les nombres premiers." Acta Math. 17, 301-314, 1893.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, p. 46, 1999.Mathews, G. B. Ch. 10 in Theory of Numbers. New York: Chelsea, 1961.Meissel, E. D. F. "Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen." Math. Ann. 25, 251-257, 1885.Riesel, H. "Meissel's Formula." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 12-13, 1994.Séroul, R. "Meissel's Formula." §8.7.3 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 179-181, 2000.

Referenced on Wolfram|Alpha

Meissel's Formula

Cite this as:

Weisstein, Eric W. "Meissel's Formula." From MathWorld--A Wolfram Web Resource.

Subject classifications