上节学习的是求一个数$n$的欧拉函数，因为用的试除法，所以时间复杂度是$O(\sqrt{n})$，如果要求$m$个数的欧拉函数，那么就会花$O(m\sqrt{n})$的时间。如果是求连续一批数的欧拉函数，可以用筛法进行优化。

筛法求欧拉函数原理

在线性筛求质数时可以顺便把每个数的欧拉函数筛出来。根据线性筛过程，一个数要么是质数被pick出来，要么是合数被筛掉，一共有这样三个地方：

1. 从筛子（st数组）里发现$i$是一个质数
2. 合数$primes[j]\ast i$被筛掉，其中质数$primes[j]$同时也是$i$的质因子（按照线性筛，也一定是最小质因子）
3. 合数$primes[j]\ast i$被筛掉，其中质数$primes[j]$不是$i$的质因子（仅仅是$primes[j]\ast i$的最小质因子）

三种情况合起来就不多不少地包含了从$1$到$n$的所有数字。

• 对于情况1，质数$i$的欧拉函数根据定义就是除了$i$之外的那$i-1$个数，因为它们一定都和$i$互质，所以$\varphi (i)=i-1$
• 对于情况2，因为$primes[j]$也是$i$的质因子，根据欧拉公式，除了第一项外剩下那些用1减的项，都只和质因子有关，和质因子的指数无关，因此相比$\varphi (i)$，$\varphi (primes[j]\ast i)$只有第一项从$i$变成了$primes[j]\ast i$
• 对于情况3，因为$primes[j]$是一个质数而且和$i$互质，因此$\varphi (primes[j]\ast i)$的公式里，除了第一项要变成$primes[j]\ast i$，还因为添加了一个新的质数$primes[j]$所以要乘以一个$1-\frac{1}{primes[j]}$，所以总共要乘以$primes[j]-1$

例题：AcWing 874. 筛法求欧拉函数

只要利用线性筛的模板和上面的结论，在三个地方填空即可。

#include <iostream>using namespace std;typedef unsigned long long ULL;const int N = 1e6 + 10;int primes[N], cnt;
bool st[N];
int eulars[N];int main() {int n; cin >> n;eulars[1] = 1;for (int i = 2; i <= n; i ++ ) {if (!st[i]) {primes[cnt ++ ] = i;// i是质数，从1到i-1都和i互质eulars[i] = i - 1;}for (int j = 0; primes[j] * i <= n; j ++ ) {st[primes[j] * i] = true;if (i % primes[j] == 0) {// primes[j]是i的质因子，欧拉公式里只要变第一项eulars[primes[j] * i] = eulars[i] * primes[j];break;}// primes[j]不是i的质因子，欧拉公式里要变第一项和(1-1/primes[j])那项eulars[primes[j] * i] = eulars[i] * (primes[j] - 1);}}ULL res = 0;for (int i = 1; i <= n; i ++ ) {res += eulars[i];}cout << res << endl;return 0;
}