# What is the “purely elementary reasoning” that the number of distinct prime factors of $n$ grows like $\frac{\log n}{\log \log n}$? [duplicate]

At the top of the second page of this paper by Ramanujan, he states that "by purely elementary reasoning", where $f(n)$ is the number of distinct prime factors of $n$, we have that for all $\varepsilon > 0$, $$f(n) < (1+\varepsilon)\frac{\log n}{\log \log n}$$ for all sufficiently large $n$, and $$f(n) > (1-\varepsilon) \frac{\log n}{\log \log n}$$ for infinitely many values of $n$, so that the maximum order of $f(n)$ is $$\frac{\log n}{\log \log n}.$$ What's the simple reason for this he had in mind?

Thanks.

Edit: notation clarified per Thomas Andrews' comment.

## marked as duplicate by Dietrich Burde, Daniel Fischer♦Jul 6 '17 at 14:56

• In older mathematical writing, "elementary" didn't necessarily mean "simple" - it just meant that the result in question could be proven with real-analytic techniques (as opposed to complex-analytic). – MathematicsStudent1122 Jul 6 '17 at 13:44
• I'm not sure that $\sim$ is the right symbol, at least as usually used. But it might be an upper bound. – Thomas Andrews Jul 6 '17 at 13:45
• my first thought is that the en.wikipedia.org/wiki/Prime_number_theorem says that there are roughly ${N}\over{log(n)}$ primes up to N and maybe taking the log of this results in the formula ? – user451844 Jul 6 '17 at 14:02
• @MathematicsStudent1122 Interesting, thanks. – Derek Allums Jul 6 '17 at 14:04
• @ThomasAndrews I think you're right, and have edited the question. – Derek Allums Jul 6 '17 at 14:04

$\omega(n)$ is maximized by primorials, and by the prime number theorem $p_k\sim k\log k$ $$\prod_{k=1}^{n}p_k = \exp\sum_{k=1}^{n}\log p_k \stackrel{\text{Stirling}}{\sim}\exp\left(n\log n + n\log\log n\right)$$ so $\omega(n)<(1+\varepsilon)\frac{\log n}{\log\log n}$ follows by considering primorials. On the other hand the square-free numbers have a positive density ($\frac{6}{\pi^2}$) in $\mathbb{N}$ and loosely speaking the previous bound does not change by much if a primorial is replaced by a square-free number with a lot of small prime factors. The bound $\omega(n)>(1-\varepsilon)\frac{\log n}{\log\log n}$ can so be achieved by considering square-free numbers.