Legendre's Formula

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.

REFERENCES:

Séroul, R. "Legendre's Formula" and "Implementation of Legendre's Formula." §8.7.1 and 8.7.2 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-179, 2000.