Legendre prime-counting formula

ID: legendre-prime-counting-formula

For , let be the primes at most . The inclusion-exclusion principle counts unsieved positive integers by . These are and the remaining primes, since every composite number has a prime factor at most its square root. Hence for . This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.

New to topics? Read the docs here!