Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 3 / 1H (Number Theory)

Let $p_1,\dots ,p_a$ be the first $a$ primes, and let $\varphi (x,a)$ count positive integers at most $x$ not divisible by any of them. The inclusion-exclusion principle givesFor $a=\pi (\sqrt{x})$, every composite at most $x$ is removed, so the survivors are one and the primes larger than $\sqrt{x}$. Thus the Legendre prime-counting formula is $\boxed{\pi (x)=\varphi (x,\pi (\sqrt{x}))+\pi (\sqrt{x})-1}$. This is the prime-counting formula, distinct from the factorial-valuation formula of the same name.

Fix $y\ge 2$ and put $a=\pi (y)$. Every prime exceeding $y$ is among the unsieved integers. Replacing each floor in the finite sum by its argument makes an error bounded by $2^a$, givingTake $x\to \infty$ with $y$ fixed. The supplied product estimate gives $0\le \mathrm{limsup}\pi (x)/x\le 1/\log y$. Since $y$ can be arbitrarily large, $\boxed{\underset{x\to \infty }{\lim }\pi (x)/x=0}$. The order of these limits avoids treating the growing inclusion-exclusion error as negligible.