In mathematics, the Hardy–Ramanujan theorem, proved by Ramanujan and checked by Hardy^[1] states that the normal order of the number ω(n) of distinct prime factors of a number n is log(log(n)).

Roughly speaking, this means that most numbers have about this number of distinct prime factors.

A more precise version states that for every real-valued function ψ(n) that tends to infinity as n tends to infinity

${\displaystyle |\omega (n)-\log \log n|<\psi (n){\sqrt {\log \log n}}}$

or more traditionally

${\displaystyle |\omega (n)-\log \log n|<{(\log \log n)}^{{\frac {1}{2}}+\varepsilon }}$

for almost all (all but an infinitesimal proportion of) integers. That is, let g(x) be the number of positive integers n less than x for which the above inequality fails: then g(x)/x converges to zero as x goes to infinity.

A simple proof to the result Turán (1934) was given by Pál Turán, who used the Turán sieve to prove that

${\displaystyle \sum _{n\leq x}|\omega (n)-\log \log x|^{2}\ll x\log \log x\ .}$

The same results are true of Ω(n), the number of prime factors of n counted with multiplicity. This theorem is generalized by the Erdős–Kac theorem, which shows that ω(n) is essentially normally distributed.