## 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 gives
 (2)
where is the Prime Counting Function. 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)

where is the Totient Function, and
 (5)

where . If , then
 (6)

Note that is not practical for computing for large arguments. A more efficient modification is Meissel's Formula.