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.