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?

  • $\begingroup$ 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.$ $\endgroup$
    – Will Jagy
    Nov 28, 2014 at 17:55

1 Answer 1


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.

  • $\begingroup$ how do you know that $log(log(n_k))=log( 1+o(1) k log(k) ) ?$ $\endgroup$ Sep 6, 2016 at 21:18
  • 1
    $\begingroup$ @usere5225321 It is written in the answer, it follows from the PNT. $\endgroup$ Sep 7, 2016 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.