Prime-counting function

The prime-counting function $\pi (X)$ is the number of primes at most $X$.

Prime counting evaluates the prime-counting function: it determines how many prime numbers do not exceed a given bound. A number-theoretic sieve can construct the whole table up to a moderate bound, while methods such as the Lehmer prime-counting algorithm group whole classes of integers to evaluate much larger arguments without listing every prime number.

A prime counting algorithm that evaluates $\pi (x)$ by recursively counting integers not divisible by the first few primes and correcting for products of larger primes. A small number-theoretic sieve and cached recursive values allow it to handle inputs much larger than the precomputed table.

For $a=\pi (\sqrt{x})$, let $p_1,\dots ,p_a$ be the primes at most $\sqrt{x}$. The inclusion-exclusion principle counts unsieved positive integers by $\varphi (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)=\varphi (x,a)+a-1$ for $x\ge 2$. This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.

If $P(X)\le A^X$ for every $X\ge 1$, where $A>1$, thenfor $X\ge 2$. Every prime in $(\sqrt{X},X]$ contributes at least $\sqrt{X}$ to the primorial, soTaking logarithms, using $\pi (\sqrt{X})\le \sqrt{X}$, and observing that $\log X\le \sqrt{X}$ for $X\ge 2$ proves the claim.