Let’s suppose that \(\forall x \in \mathbb{N}\), \(\nu(x)\) counts the number of unique prime divisors of \(x\). Given \(A = [1,n]\), for all \(\epsilon \in (0,1)\) there exists a constant \(c > 0\) such that at least \(1-\epsilon\) of the integers in \(A\) satisfy:

\begin{equation} \forall x \in A, |\nu(x)- \log \log n| \leq c \cdot \sqrt{\log\log n} \end{equation}

as \(n \to \infty\).

Turan’s proof:

If we randomly choose \(x \in [1,n]\), for any prime \(p\) let’s define the indicator variable \(X_p\) where \(X_p = 1\) if \(p|x\) and \(X_p=0\) otherwise. So the number of prime divisors of \(x\) less than or equal to \(M\) is approximately:

\begin{equation} X = \sum_{p \leq M} X_p \end{equation}

Now, if we pick \(M = \sqrt{n}\) there are at most two prime factors of \(x\) larger than \(M\) so we have:

\begin{equation} \nu(x) - 2 \leq X \leq \nu(x) \end{equation}

Moreover, from a frequentist perspective we have:

\begin{equation} \mathbb{E}[X_p] = 1 \cdot \frac{1}{p} + 0 \cdot \big(1-\frac{1}{p}\big) = \frac{1}{p} \end{equation}

and therefore:

\begin{equation} \mathbb{E}[X] = \sum_{p \leq M} \frac{1}{p} = \log \log M = \log \log n + \mathcal{O}(1) \end{equation}

due to Mertens’ second theorem.

As for the variance of \(X\) we have:

\begin{equation} \text{Var}[X] = \sum_{p \leq M} \text{Var}[X_p] + \sum_{p \neq q} \text{Cov}[X_p,X_q] \end{equation}

and due to the fact that \(\frac{1}{pq} << \min \big(\frac{1}{p}, \frac{1}{q}\big)\) for large primes \(p\) and \(q\):

\begin{equation} \text{Cov}[X_p,X_q] = \mathbb{E}[X_p] \cdot \mathbb{E}[X_q] - \mathbb{E}[X_p \cdot X_q] \approx 0 \end{equation}

It follows that the variance is given by:

\begin{equation} \text{Var}[X] = \log\log n + \mathcal{O}(1) \end{equation}

and so by Chebyshev’s inequality we have:

\begin{equation} P(|\nu(x) - \log \log n| \geq \lambda \cdot \sqrt{\log \log n}) \leq \frac{1}{\lambda^2} \end{equation}


  1. Hardy, G. H.; Ramanujan, S. (1917), “The normal number of prime factors of a number n”, Quarterly Journal of Mathematics
  2. Weisstein, Eric W. “Mertens’ Second Theorem.” From MathWorld–A Wolfram Web Resource.