线性筛复习

线性筛素数

普通的埃氏筛是用一个数来筛掉它的倍数，它的倍数就一定是合数
这样的话一个数可能会被筛很多次
线性筛就优化在这个地方，它保证每个合数一定被它最小的因子筛掉
注意是范围的话会爆

bz[i]表示是不是素数, pri[i]记下每个素数
for (ll i = 2; i <= n; i++) {
if (!bz[i]) pri[++cnt] = i;
for (ll j = 1; j <= cnt and i * pri[j] <= n; j++) {
bz[i * pri[j]] = 1;
if (i % pri[j] == 0) break; //关键
}
}

上面那句关键就保证了每个数只被它最小的因子筛掉
因为这个数组是单调递增的

线性筛欧拉函数

线性筛的同时还可以维护很多信息，因为线性筛可以做到不重不漏统计到每个数
比如另一个经典应用，在线性筛素数的同时筛出欧拉函数
相比上面的代码，就表示
为素数时显然只有和这两个因子，所以
当是的最小因子的时候，，证明就不写了我懒
当与互质的时候，欧拉函数是积性函数，所以
也可以写成下面的那种形式，这是由上面的证明推导来的
两种写法都是正确的

for (ll i = 2; i <= n; i++) {
if (!bz[i]) pri[++cnt] = i, phi[i] = i - 1;
for (ll j = 1; j <= cnt and i * pri[j] <= n; j++) {
bz[i * pri[j]] = 1;
if (i % pri[j] == 0) {phi[i * pri[j]] = phi[i] * pri[j]; break;}
else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}