线性筛复习

线性筛素数

普通的埃氏筛是用一个数来筛掉它的倍数，它的倍数就一定是合数

这样的话一个数可能会被筛很多次

线性筛就优化在这个地方，它保证每个合数一定被它最小的因子筛掉

注意是范围的话会爆

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);
  }
}