How to prove an asymptotic formula for the number of distinct prime factors of an integer?

Question

Let $\omega(n)$ be the number of distinct prime factors of an integer $n$. I need to show that the sum $\sum_{x\le n}\omega(x)$ is $$n\log\log n+bn+O\left(\frac{n}{\log n}\right)$$ Any solutions or link to existing solutions to this problem is most welcome.

Answer 1

Following the logic of H&W the sum in question is \begin{equation} \sum_{n \leq x}\omega(n) = \sum_{n \leq x}\sum_{p \mid n}1 \end{equation} by definition of $\omega(n)$, Switching the order of summation gives \begin{equation} \sum_{p \leq x} \sum_{\substack{n \leq x \\ p \mid n}} 1 \end{equation}

It shouldn't be too hard to see that the inner sum, being the number of multiples of $p$ which are no greater than $x$ is simply $[x/p]$ (where the square brackets represent the integer part).

We can get rid of the square brackets at the cost of an error of size $O(1)$ (actually the error will either be $0$ or $1$ but this is a nicer cover-all). Therefore our sum is \begin{equation} \sum_{p \leq x}\left(\frac{x}{p} + O(1)\right) = x\sum_{p \leq x}1 + O(\pi(x)) \end{equation} and the result follows from Mertens theorem which states \begin{equation} \sum_{p \leq x} \frac{1}{p} = \log \log x + B_1 + O\left(\frac{1}{\log x}\right) \end{equation}