TOPICS
Search

Meissel's Formula

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

|_x_|=1+sum_(1<=i<=a)|_x/(p_i)_|-sum_(1<=i<j<=a)|_x/(p_ip_j)_|+sum_(1<=i<j<k<=a)|_x/(p_ip_jp_k)_|-...+pi(x)-a+P_2(x,a)+P_3(x,a)+...,
(1)

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

P_2(x,a)=sum[pi(x/(p_i))-(i-1)]
(2)

for p_a<p_i<=sqrt(x) and

P_3(x,a)=sum_(i>a)P_2(x/(p_i),a)
(3)
=sum_(i=a+1)^(c)sum_(j=i)^(pi(sqrt(x/p_i)))[pi(x/(p_ip_j))-(j-1)].
(4)

Meissel's formula is

pi(x)=|_x_|-sum_(i=1)^c|_x/(p_i)_|+sum_(1<=i<j<=c)|_x/(p_ip_j)_|-...+1/2(b+c-2)(b-c+1)-sum_(c<i<=b)pi(x/(p_i)),
(5)

where

b=pi(x^(1/2))
(6)
c=pi(x^(1/3)).
(7)

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

References

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. https://mathworld.wolfram.com/MeisselsFormula.html

Subject classifications