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

本题更新后，数据经过了加强，必须使用线性复杂度$O(N)$的筛法。 ------------ ```cpp #include<cstdio> #include<iostream> using namespace std; int main() { int n, q, check[100000001]={0}; int prime[1000001],cnt=0; //根据n<=10^8,q<=10^6开对应的数组大小，防止MLE //初始将check数组全部标记为0，标0的是素数，标1的不是素数 scanf("%d%d",&n,&q); check[1]=1;//1不是素数 for(int i=2;i<=n;i++) { if(!check[i])prime[cnt++]=i;//若当前数i没有被之前的所有数筛掉，表明i是素数，将i添加进素数表prime for(int j=0;j<cnt&&i*prime[j]<100000001;j++)//注意i*prime[j]不要超过n的上限（10^8） { check[i*prime[j]]=1;//将当前素数prime[j]的i倍标记为合数 if(i%prime[j]==0)break;//关键步骤：保证每个合数只被筛一次 } } for(int i=1;i<=q;i++) { scanf("%d",&n); printf("%d\n",prime[n-1]);//由于素数表从0开始存，所以输出时下标应减1 } return 0; } ``` ------------ ### 算法原理 素数筛法的原理：把不是素数的筛掉，剩下的就都是素数。 欧拉线性筛的关键在于：**每个合数只被它最大的非自身的因数筛掉**。 例如： $12$不会被$4$筛掉，而是被$6$筛掉； $45$不会被$9$筛掉，而是被$15$筛掉。 |当前用于筛素数的数i | 被i筛掉的数 |被i筛掉的数 |被i筛掉的数 |被i筛掉的数 | | :----------: | :----------: | :----------: | :----------: | :----------: | |2 |2 * 2=4 | | | | |3 |3 * 2=6 |3 * 3=9 | | | |4 |4 * 2=8 | | | | |5 |5 * 2=10 |5 * 3=15 |5 * 5=25 | | |6 |6 * 2=12 | | | | |7 |7 * 2=14 |7 * 3=21 |7 * 5=35 |7 * 7=49 | |8 |8 * 2=16 | | | | |9 |9 * 2=18 |9 * 3=27 | | | |10 |10 * 2=20 | | | | ------------ ### 模拟程序运行过程 我们以 **$12$不被$4$筛掉而被$6$筛掉** 为例： 当 $i$ 循环执行到 $i=4$ 时： 素数表$prime$中已有两个素数：$2$和$3$。 此时在$check$数组中已经被标记为$1$的数（合数）是：$4$、$6$、$9$。 因为$i=4$已经被标记为$1$，所以我们不将$4$添加进素数表$prime$。 此时执行 $j$ 循环： 因为素数表$prime$中有$2$和$3$，所以预计将要被筛掉的数是$4 \times 2 = 8$ 和 $4 \times 3 = 12$。 当$4 \times 2 = 8$被筛掉以后，经过 $i \bmod prime[j]=0$ 判断可以知道$4\bmod2=0$， 此时应结束 $j$ 循环，不再筛 $4 \times 3 = 12$。 ------------ ### 关键步骤解释 我们都知道$12$的最大因数（非自身，下同）是$6$，因此$12$应该被$6$筛掉，那么上述判断的原理是什么呢？ **因为当出现 $i \bmod prime[j] = 0$ 的情况时，意味着$prime[j]$ 是 $i$ 的一个因数（$2$是$4$的一个因数）。** **既然$4$是$12$的因数，$2$又是$4$的因数，所以$2$也是$12$的因数。** **由此可以知道，$4$不是$12$的最大因数，$12$的最大因数会在后面出现，即$2$所对应的$6$，$12$将会在$i=6$时被筛掉。** 同理可以判断：$9$是$45$的因数，$3$又是$9$的因数，所以$3$也是$45$的因数，$9$不是$45$的最大因数，$45$的最大因数将会在后面出现，即$3$所对应的$15$，$45$将会在$i=15$时被筛掉。 ------------ ### 注意 此方法空间开销较大，注意内存溢出。 数据量大，建议使用 $scanf$ ， $printf$ 函数进行读写操作。 ------------ 第一次写题解，不足之处请指出。