769. 筛法求欧拉函数
时间限制：1000 MS 内存限制：64 MB
题目描述
# 筛法求欧拉函数 ## 题目描述 给定一个正整数 $n$，求 $1$ 到 $n$ 中所有整数的欧拉函数之和，即 $$ \sum_{i=1}^{n}\varphi(i)。 $$ 其中，欧拉函数 $\varphi(m)$ 表示不超过正整数 $m$ 且与 $m$ 互质的正整数的个数，规定 $\varphi(1)=1$。 ## 输入格式 从文件 `totient.in` 中读入数据。 共一行，包含一个整数 $n$。 ## 输出格式 输出到文件 `totient.out`。 共一行，输出一个整数，表示 $\sum_{i=1}^{n}\varphi(i)$。 ## 数据范围 对于所有测试数据，$1 \le n \le 10^6$。 答案可能超过 $32$ 位整数的表示范围，请使用 $64$ 位整数存储。 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。 ## 样例输入 ``` 6 ``` ## 样例输出 ``` 12 ``` ## 样例说明 $\varphi(1),\varphi(2),\ldots,\varphi(6)$ 分别为 $1,1,2,2,4,2$，它们的和为 $12$。