- 埃氏筛，时间复杂度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 }