T349752 筛法求欧拉函数

#### 欧拉函数的定义 > $1∼N$ 中与 $N$互质的数的个数被称为欧拉函数，记 $ϕ(N)$。 > > 若在唯一分解定理中，$N={p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_n}^{\alpha_n}$，则有： > > $ϕ(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_n})$

给定一个正整数 $n$，求 $1∼n$ 中每个数的欧拉函数之和。

共一行，包含一个整数 $n$。

共一行，包含一个整数，表示 $1∼n$ 中每个数的欧拉函数之和。

#### 数据范围 $1≤n≤10^6$