TOPICS
Search

Lehmer's Formula


Lehmer's formula is a formula for the prime counting function,

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

where |_x_| is the floor function,

a=pi(x^(1/4))
(2)
b=pi(x^(1/2))
(3)
b_i=pi(sqrt(x/p_i))
(4)
c=pi(x^(1/3)),
(5)

and pi(n) is the prime counting function. It is related to Meissel's formula.


See also

Meissel's Formula, Prime Counting Function

Explore with Wolfram|Alpha

References

Riesel, H. "Lehmer's Formula." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 13-14, 1994.

Referenced on Wolfram|Alpha

Lehmer's Formula

Cite this as:

Weisstein, Eric W. "Lehmer's Formula." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LehmersFormula.html

Subject classifications