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.

Wolfram Web Resources