In mathematics, the Hardy–Ramanujan theorem, proved by Ramanujan and checked by Hardy[1] states that the normal order of the number
of distinct prime factors of a number
Roughly speaking, this means that most numbers have about this number of distinct prime factors.
A more precise version[2] states that for every real-valued function
for almost all (all but an infinitesimal proportion of) integers.
be the number of positive integers
for which the above inequality fails: then
A simple proof to the result was given by Pál Turán, who used the Turán sieve to prove that[3]
The same results are true of
, the number of prime factors of
counted with multiplicity.
This theorem is generalized by the Erdős–Kac theorem, which shows that
is essentially normally distributed.
There are many proofs of this, including the method of moments (Granville & Soundararajan)[4] and Stein's method (Harper).
[5] It was shown by Durkan that a modified version of Turán's result allows one to prove the Hardy–Ramanujan Theorem with any even moment.