素数筛

• 埃氏筛，时间复杂度o(n*log(log2n))，接近线性

1     for (int i = 2; i <= n / i; i++)
2         if (!pri[i])//若i未被筛掉则必定是质数
3             for (int j = i * i; j <= n; j += i)//枚举i的倍数必定是合数
4                 pri[j] = 1;

• 欧拉筛（线性筛），时间复杂度o(n)

1     int cnt = 0;
2     for (int i = 2; i <= n; i++){
3         if (!pri[i])p[++cnt] = i;
4         for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
5             pri[i * p[j]] = 1;//筛掉整数倍
6             if (i % p[j] == 0)break;//后面会在次出现，目前不用筛
7         }
8     }