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.
