Legendre's formula counts the number of positive integers less than or equal to a number which are not divisible by any of the first primes,
(1)
where is the floor function. Taking , where is the prime counting function, gives
(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
(3)
Let , then
where is the totient function, and
(9)
where . If , then
(10)
Note that is not practical for computing for large arguments. A more efficient modification is Meissel's formula.
See alsoLehmer's Formula,
Mapes' Method,
Meissel's Formula,
Prime Counting Function Explore with Wolfram|Alpha ReferencesSé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|AlphaLegendre's Formula Cite this as:Weisstein, Eric W. "Legendre's Formula." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LegendresFormula.html
Subject classificationsRetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4