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
(4)
| |||
(5)
| |||
(6)
| |||
(7)
| |||
(8)
|
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.