Legendre's formula counts the number of positive integers less than or equal to a real number 
which are not divisible
by any of the first 
primes, where 
is a nonnegative integer,
 |
(1)
|
where 
is the floor function. For 
, 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.
For a nonnegative integer 
, let 
, where 
is the 
th prime, with 
. The inclusion-exclusion
principle gives the compact equivalent form
 |
(3)
|
where 
is the Möbius function and the sum
is over the positive divisors of 
. Indeed, 
is 1 when 
is relatively prime to
and 0 otherwise. Summing this indicator function
over 
and interchanging the two finite sums gives the formula.
For 
,
Legendre's formula satisfies the recurrence relation
 |
(4)
|
Let 
,
then
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(9)
|
where 
is the totient function, and
 |
(10)
|
where 
.
If 
,
then
 |
(11)
|
Legendre's formula is not practical for computing 
for large arguments. A more efficient modification is
Meissel's formula.
