关于线性筛欧拉函数的相关证明

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