TOPICS
Search

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

 phi(x,a)=phi(x,a-1)-phi(x/(p_a),a-1).
(3)

Let m_k=p_1p_2...p_k, then

phi(m_k,k)=|_m_k_|-sum|_(m_k)/(p_i)_|+sum|_(m_k)/(p_ip_j)_|-...
(4)
=m_k-sum(m_k)/(p_i)+sum(m_k)/(p_ip_j)-...
(5)
=m_k(1-1/(p_1))(1-1/(p_2))...(1-1/(p_k))
(6)
=product_(i=1)^(k)(p_i-1)
(7)
=phi(m_k),
(8)

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 Function

Explore with Wolfram|Alpha

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 Formula

Cite this as:

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

Subject classifications