prime counting function $\pi(x)$ is $o(x)$

Question

What's the simplest and/or shortest proof that $\lim_{x \to \infty} \frac{\pi(x)}{x} = 0$, where $\pi(x)$ is the prime counting function? I'm curious to see if there's a slick proof that is simpler and shorter than Chebyshev's proof that $\pi(x) \asymp \frac{x}{\log x} \ (x \to \infty)$. Of course, using the prime number theorem to prove it is cheating. In particular, can it be proved using a simple idea like the sieve of Eratosthenes?

Answer 1

Fix a positive integer $n$ and consider the canonical map $f:\Bbb N \rightarrow \Bbb Z / n \Bbb Z$.

It is clear that any prime number $p > n$ lies in the inverse image $f^{-1}((\Bbb Z/n\Bbb Z)^\times)$, which shows that $\limsup_{x\rightarrow\infty} \frac{\pi(x)}x \leq \frac{\phi(n)}n$, where $\phi(n)$ is the Euler totient function.

Taking $n$ to be the product of the first $k$ prime numbers, we are reduced to showing that $S = \prod_p (1 - \frac 1 p)$ is equal to $0$, where the product ranges over all prime numbers $p$.

But $S^{-1}$ is the sum of the harmonic series $\sum_{m \geq 1}\frac 1 m$, which is $\infty$. Therefore $S = 0$, finishing the proof.

---

_{The last steps could be written more rigorously, but here I emphasize on the idea.}