•   Wikis

# Erdős–Kac theorem: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

# Encyclopedia

In number theory, the Erdős–Kac theorem, named after Paul Erdős and Mark Kac, and also known as the fundamental theorem of probabilistic number theory, states that if ω(n) is the number of distinct prime factors of n, then for any fixed a < b,

$\lim_{x \rightarrow \infty} \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{\omega(n) - \log \log n}{\sqrt{\log \log n}} \le b \right\} \right ) = \Phi(a,b)$

where Φ(a,b) is the normal (or "Gaussian") distribution, defined as

$\Phi(a,b)= \frac{1}{\sqrt{2\pi}}\int_a^b e^{-t^2/2} \, dt$

Stated somewhat heuristically, what Erdős and Kac proved was that if n is a randomly chosen large integer, then the number of distinct prime factors of n has approximately the normal distribution with mean and variance $\log \, \log \, n$ for

This means that the construction of a number around one billion requires on average three primes.
For example 1,000,000,003 = 23 × 307 × 141623.

n Number of

Digits in n

Average number

of distinct primes

standard

deviation

1,000 4 2 1.4
1,000,000,000 10 3 1.7
1,000,000,000,000,000,000,000,000 25 4 2
1065 66 5 2.2
109,566 9,567 10 3.2
10210,704,568 210,704,569 20 4.5
101022 1022 50 7.1
101044 1044 100 10
1010434 10434 1000 31.6

## References

• Paul Erdős and Mark Kac, "The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions", American Journal of Mathematics, volume 62, No. 1/4, (1940), pages 738–742.