欧拉筛（线性筛）是数论选手的必备技能。它不仅能筛素数，还能顺便求出欧拉函数 φ 和莫比乌斯函数 μ。今天一文搞定所有模板。
欧拉筛代码（求素数 + phi + mu）
const int N = 1e6 + 5;
int primes[N], cnt;
bool isComp[N];
int phi[N], mu[N];
void euler_sieve(int n) {
phi[1] = 1;
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!isComp[i]) {
primes[++cnt] = i;
phi[i] = i - 1;
mu[i] = -1;
}
for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
int v = i * primes[j];
isComp[v] = true;
if (i % primes[j] == 0) {
// primes[j] 是 i 的最小质因子
phi[v] = phi[i] * primes[j];
mu[v] = 0;
break;
} else {
phi[v] = phi[i] * (primes[j] - 1);
mu[v] = -mu[i];
}
}
}
}关键理解
- 欧拉函数
φ(n)：小于等于n且与n互质的数的个数。 - 莫比乌斯函数
μ(n)：若n有平方因子则μ=0；否则若质因子个数为奇数则μ=-1，偶数则μ=1。
线性筛的精髓：每个合数 只被它的最小质因子 筛掉，所以复杂度是严格的 O(n)。
常见应用场景
- 求逆元：
inv[i] = (mod - mod/i) * inv[mod % i] % mod（配合质数）。 - 莫比乌斯反演：解决
gcd计数问题（如求[1,n]中互质数对个数）。 - 杜教筛：在亚线性时间内求积性函数前缀和（竞赛进阶）。
给新手的建议
先背下欧拉筛的板子，然后做两道题：P2158 [SDOI2008] 仪仗队（欧拉函数）和 P2522 [HAOI2011] Problem b（莫比乌斯反演）。做完这两道，数论的大门就向你敞开了。
实战小贴士
- 数组大小：欧拉筛需要
isComp、phi、mu三个数组，内存约为3 * N * 4字节，N=1e7时约 120MB，注意题目内存限制。 - 初始化：别忘了设置
phi[1] = mu[1] = 1，否则积性函数前缀和会出错。 - 溢出问题：循环条件
i * primes[j] <= n可能溢出 int，建议写成i <= n / primes[j]。