洛谷题解 | P3383 【模板】线性筛素数

题目思路

先思考最朴素的素数筛法。即对于每个数 \(n\)，检查它是否能被任意小于 \(\sqrt{n}\) 的整数整除。如果不能，则 \(n\) 是素数。这种筛法显然是低效的。
逆向思考，上述素数筛思路为验证每个数是否为质数，那可不可以排除所有合数，这样剩下的自然是质数了？这就是埃氏筛。
埃氏筛的思想是：从 \(2\) 开始，将除了它本身所有 \(2\) 的倍数划掉，然后是 \(3\)、\(4\)、\(\dots\) 重复此过程，直到\(\sqrt{n}\)，剩下的数就是小于 \(n\) 的所有素数。
这种筛法的复杂度为 \(\mathcal O(n \log \log n)\)。那如何做到 \(\mathcal O(n)\) 的复杂度？
观察发现，埃氏筛会重复筛除质数。如果每个合数仅被其最小质因数筛除一次，那就不会被重复筛除，也就是做到 \(\mathcal O(n)\) 了。这便是欧拉筛。
维护一个质数数组，对于每个新数，首先检查它是否是质数，若是则加入数组。接着用当前质数数组中的数去标记合数，当发现当前数能被某个质数整除时立即终止标记过程。这一点十分关键，它保证每个合数仅被其最小质因数筛除，也就只被筛除一次。
有人可能还是不明白为什么是这时候退出。确保每个合数仅被其最小质因数筛除一次，就是 \(i \times prime_{j}\) 不能拥有比 \(prime_{j}\) 更小的质因子，也就是  \(i\) 不能拥有比 \(prime_{j}\) 更小的质因子。如果发现 \(i\) 的最小质因子已经是 \(prime_{j}\) 了，此时不退出，下一轮循环的 \(prime_{j}\) 增大，\(i\) 中就有比它更小的质因子，于是就无法确保每个合数仅被其最小质因数筛除一次了。
欧拉筛因为每个合数仅被其最小质因数筛除一次，所以复杂度是 \(\mathcal O(n)\) 的。
AC 代码

[code]#include using namespace std;int n,q,cnt = 0,prime[100000010];bool isprime[100000010]; int main(){        std::ios::sync_with_stdio(0);        cin >> n >> q;        memset(isprime,true,sizeof(isprime));        for(int i = 2;i