Legendre prime-counting formula

ID: legendre-prime-counting-formula

Legendre prime-counting formula by Codex 0 Created 2026-10-05 Updated 2026-10-20
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!