Legendre's Formula
Legendre's formula counts the number of positive integers less than or equal to a number x which are not divisible by any of the first a primes,
| phi(x,a)=|_x_|-sum|_x/(p_i)_|+sum|_x/(p_ip_j)_|-sum|_x/(p_ip_jp_k)_|+..., |
(1)
|
where |_x_| is the floor function. Taking a=pi(sqrt(x)), where pi(n) is the prime counting function, gives
| phi(x,pi(sqrt(x)))=pi(x)-pi(sqrt(x))+1=|_x_|-sum_(p_i<=sqrt(x))|_x/(p_i)_|+sum_(p_i<p_j<=sqrt(x))|_x/(p_ip_j)_|-sum_(p_i<p_j<p_k<=sqrt(x))|_x/(p_ip_jp_k)_|+.... |
(2)
|
Legendre's formula holds since one more than the number of primes in a range equals the number of integers minus the number of composites in the interval.
Legendre's formula satisfies the recurrence relation
Let m_k=p_1p_2...p_k, then
where phi(n) is the totient function, and
| phi(sm_k+t,k)=sphi(m_k)+phi(t,k), |
(9)
|
where 0<=t<=m_k. If t>m_k/2, then
| phi(t,k)=phi(m_k)-phi(m_k-t-1,k). |
(10)
|
Note that phi(n,n) is not practical for computing pi(n) for large arguments. A more efficient modification is Meissel's formula.
See also
Lehmer's Formula, Mapes' Method, Meissel's Formula, Prime Counting FunctionExplore with Wolfram|Alpha
More things to try:
References
Séroul, R. "Legendre's Formula" and "Implementation of Legendre's Formula." §8.7.1 and 8.7.2 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-179, 2000.Referenced on Wolfram|Alpha
Legendre's FormulaCite this as:
Weisstein, Eric W. "Legendre's Formula." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LegendresFormula.html