= Legendre prime-counting formula
{c}
{title2=$\pi(x)=\phi(x,\pi(\sqrt x))+\pi(\sqrt x)-1$}
For $a=\pi(\sqrt x)$, let $p_1,\ldots,p_a$ be the <primes> at most $\sqrt x$. The <inclusion-exclusion principle> counts unsieved positive <integers> by $\phi(x,a)=\sum_S(-1)^{|S|}\lfloor x/\prod_{i\in S}p_i\rfloor$. These are $1$ and the remaining <primes>, since every <composite number> has a <prime factor> at most its square root. Hence $\pi(x)=\phi(x,a)+a-1$ for $x\geq2$. This is a prime-counting identity, distinct from the <Legendre formula> for factorial valuations.
Back to article page
