[AcWing]868. 筛质数（C++实现）线性筛模板题

质数（C++实现）线性筛模板题"/>

[AcWing]868. 筛质数（C++实现）线性筛模板题

[AcWing]868. 筛质数（C++实现）线性筛模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路：

线性筛法在10的6次方级数上和埃式筛法的时间差不多；在10的7次方的级数上比埃式筛法快一倍，在应用中常常使用的是线性筛法。

注：对于一个合数，它一定存在一个最小质因子

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include<iostream>
using namespace std;const int N = 1e6+10;int primes[N],cnt;
bool st[N];void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i; // 如果i是质数，加到数表里去（从小到大存放的）// 每个数只会被筛一边，因此时间是线性的for (int j = 0; primes[j] <= n / i; j ++ ) // 从小到大枚举所有质数{/*注：primes[j]简写为pjpj小于i的所有质因子，因此pj一定是pj*i的最小质因子，将pj*i筛掉*/st[primes[j] * i] = true;/*i % primes[j] == 0该条件成立时，pj一定是i的最小质因子,因此pj也一定是pj*i的最小质因子这句代码保证了每个合数只会被最小质因数筛去，将时间复杂度降到了线性如果在此时不break，则不能保证下一个primes[j+1]是primes[j+1] * i的最小质因子*/if (i % primes[j] == 0) break;}}
}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

代码中比较难以理解的地方
本题比较难以理解的地方在这段代码

        for (int j = 0; primes[j] <= n / i; j ++ ) // 1{st[primes[j] * i] = true; // 2if (i % primes[j] == 0) break; // 3}

1、最外层的循环表示，从小到大遍历所有的质数；

2、st[primes[j] * i] = true;

作用：表示用primes[j] * i的最小质因数primes[j] 筛掉primes[j] * i这个合数。

为什么可以筛掉primes[j] * i？

因为此时i % primes[j] == 0一定是未成立的，因此primes[j]一定小于i的最小质因数，因此primes[j]是primes[j]*i的最小质因数

3、if (i % primes[j] == 0) break;

为什么此处要进行break？

因为此时i % primes[j] == 0成立了，primes[j]是i的最小质因数。
如果此时不break，那么primes[j]会继续向后遍历，导致primes[j]不再是i的最小质因数，也不是primes[j] * i的最小质因数。

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

• 线性筛法

6. 总结

线性筛法筛质数的模板题，熟记并背下来。