J. Функция Эйлера решетом

Функция Эйлера $\varphi(n)$ — количество натуральных чисел от 1 до $n$, взаимно простых с $n$. Посчитайте $\sum_{i=1}^{N} \varphi(i)$.

Одно число $N$ ($1 \le N \le 10^7$).

Выведите сумму значений функции Эйлера от 1 до $N$.