Erdős–Kac theorem

Remarks

In words, $\omega(n)$ has an approximately normal distribution with mean and variance $\log\log n$. A heuristic proof: $\omega(n) = \sum_{p \le n} \mathbf{1}_{p \mid n}$, and for a random $n$ the events $p \mid n$ have probability $1/p$ and are nearly independent, so the central limit theorem applies with variance $\sum_{p \le x} 1/p \approx \log\log x$. A rigorous proof restricts to small primes, shows near independence with a sieve, and compares moments with those of the normal law. The earlier theorem of Hardy and Ramanujan says that $\omega(n)$ has normal order $\log\log n$: for every $\varepsilon > 0$, almost all $n$ satisfy $\abs{\omega(n) - \log\log n} < \varepsilon \log\log n$. Since $\log\log n$ grows very slowly, the limit is reached slowly; for $n$ near $10^{9}$, $\log\log n \approx 3$.

Going deeper

For a student

The Erdős–Kac theorem is the founding result of probabilistic number theory. It treats the indicators of divisibility by different primes as almost independent random variables, and turns this into a central limit theorem for the additive function $\omega$. The same holds for $\Omega(n)$, the number of prime factors counted with multiplicity, and more generally for many additive functions. It sharpens the Hardy–Ramanujan normal order result, which gives only the center and not the shape of the distribution.