# How to prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?

Let $$\omega(n) := \text{number of distinct primes dividing } n.$$ How can one prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?
I know that $\omega(n)! \leq n$. I feel like I could use the Prime Number Theorem $$\pi(x) \sim \frac{x}{\log(x)},$$ and that $$\pi (x) \leq 2 \frac{x}{\log(x)} = O \Big{(}\frac{x}{\log(x)} \Big{)} \quad \text{for } x \geq 3.$$ Furthermore, I know that for the primorial function $g(n) := \prod_{i=1}^{n} P_{i}$ and the prime-counting function have the following property: $\omega(g(n)) = n = \pi(P_{n}).$ Last, I know that for the theta function defined as $$\theta (X) = \sum_{\text{primes }p \leq x} \log(p)$$ we have for the $n$'th prime $\theta(P_{n}) = \log(g(n))$, and that $\pi(x) \sim \frac{\theta(x)}{\log(x)}$. Finally, I know that $\theta (x) = O(x)$.

I feel that I have enough ingredients to prove what I want to prove, but I still can't figure it out. Can you please help me?

• You just need your upper bound for the primorials themselves. The number of distinct primes dividing some $n$ is no more than the number of primes dividing the largest primorial that is less than or equal to $n.$ Nov 28, 2014 at 17:55

We can prove that$$\underset{n\rightarrow\infty}{\limsup}\frac{\omega\left(n\right)}{\log\left(n\right)/\log\left(\log\left(n\right)\right)}=1.$$ Note that $\forall k$ the least value of $n$ such that $\omega\left(n\right)=k$ is $n_{k}=p_{1}\cdots p_{k}.$ Now $\log\left(n\right)/\log\left(\log\left(n\right)\right)$ is a monotone increasing function, so it's sufficient to show that$$\underset{k\rightarrow\infty}{\limsup}\frac{k}{\log\left(n_{k}\right)/\log\left(\log\left(n_{k}\right)\right)}=1.$$ From PNT you have$$\log\left(n_{k}\right)=\underset{i=1}{\overset{k}{\sum}}\log\left(p_{i}\right)=\theta\left(p_{k}\right)\sim p_{k}\sim k\log\left(k\right)$$ and$$\log\left(\log\left(n_{k}\right)\right)=\log\left(\left(1+o\left(1\right)\right)k\log\left(k\right)\right)=\log\left(k\right)+\log\left(\log\left(k\right)\right)+\log\left(1+o\left(1\right)\right)=\log\left(k\right)\left(1+o\left(1\right)\right)$$and this complete the proof.
• how do you know that $log(log(n_k))=log( 1+o(1) k log(k) ) ?$ Sep 6, 2016 at 21:18