I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$.
How can I do this?
[Math] Upper bound number of distinct prime factors
analytic-number-theorynumber theoryprime factorizationprime numbers
Best Answer
$\omega(n)$ reaches a maximum at the primorial numbers $p\#=2\cdot3\cdot5\cdot\cdots\cdot p,$ where $\omega(p\#)=\pi(p).$ The Prime Number Theorem (in one of its forms) says that $\vartheta(x):=\log x\#\sim x,$ and so $p\#=e^{(1+o(1))p}$. If $p$ is the $n$-th prime then $p\sim n\log n$ and so $$ n=\pi(p)=\omega(p\#)=\omega(e^{(1+o(1))p})=\omega(e^{(1+o(1))(1+o(1))n\log n})=\omega(n^{(1+o(1))n}). $$
Setting $x=n^{(1+o(1))n}$ and solving for $n$ you get $$ n\sim\frac{\log x}{W(\log x)}=\frac{\log x}{W(\log x)}=\frac{\log x}{\log\log x-O(\log\log\log x)}\sim\frac{\log x}{\log\log x} $$ which has a slightly weaker error term than the quoted result.