Is there an intuitive reason why the natural logarithm shows up in the Prime Number Theorem?

Question

I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.

Answer 1

Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $\frac{1}{p}$, hence the probability that it's not divisible by $p$ is $1 - \frac{1}{p}$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is

$$\prod_{p < n} \left( 1 - \frac{1}{p} \right).$$

So we want to explain why this grows like $\frac{1}{\ln n}$. Well, let's invert it, getting

$$\prod_{p < n} \frac{1}{1 - \frac{1}{p}} = \prod_{p < n} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \dots \right).$$

Expanding this out produces a sum over terms of the form $\frac{1}{k}$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is

$$\sum_{k < n} \frac{1}{k} \sim \ln n$$

by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!