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

· · 题解

一些闲话

蒟蒻第一篇题解，这一篇题解写的时候是尽可能详细的写的，所以可能有些啰嗦的地方（求审核大大通过）。

先放代码（写了超多、超详细的注释，一定仔细看一看，深刻理解一下，别直接复制粘贴）：

ACcode：

#include<bits/stdc++.h>
#define re ree()//宏定义快读，写的时候会舒服一点。 
using namespace std;
int ree(){int f=1,k=0;char c=getchar();while(c<'0'||c>'9') {if(c == '-') f = -1;c=getchar();}while(c>='0'&&c<='9') {k=k*10+c-'0';c=getchar();}return f*k;}//快读 
bool is_pe[100000001];//标记数组，is_pre[i]表示i是否为和数（1真，0假）。 
int pe[20000001],n,q,coun;//pe[i]表示第i个质数，coun表示质数的总个数，n，q意义见题面。 
void find_prime(int n)//线性筛质数 
{
    for(int i=2;i<=n;i++)//从2开始枚举到n因为0,1都不是质数 
    {
        if(is_pe[i]==0)//如果i没被标记为和数（就是 i 为质数） 
        {
            pe[++coun]=i;//记录 i 到质数表中，质数数量 +1 
        }
        for(int j=1;j<=coun&&i*pe[j]<=n;j++)// j 从 1 枚举到 coun 同时“i*pe[j]<=n ”保证了 is_pe[i*pe[j]]不会让超过 n 的数进去，以防越界和超时 
        {
            is_pe[i*pe[j]]=1;//把 i 的所有的质数倍倍数都标记为合数 

            if(i%pe[j]==0){break;} //线性筛最关键、最核心的地方 --> 如果 i 是pe[j]的倍数，就直接跳出循环，保证了每个数只会被（它的最小质因数）筛掉一次，避免了冗余，也保证了线性复杂度，具体证明我会在证明里详细展开 

        }
    }
    return;//记得写 return 养成好习惯（避免函数类型是整型（int、longlong）或其他类型时莫名 RE 还查不出错） 
}
int main()
{
    n=re,q=re;//输入 
    find_prime(n);//线性筛 
    while(q--)
    {
        int k;
        k=re;
        printf("%d\n",pe[k]);//输出第 k 个质数 
    }
    return 0;
}

//居然写了这么多注释（bushi）

算法介绍

题目名称已经很显然了，要求使用线性筛（欧拉筛），（当然，卡常的埃氏筛也可以水过）。 讲一下欧拉筛: 它其实就类似埃氏筛的一个优化，即它保证了一个数只会被筛掉一次，以此得到线性的复杂度。

思路：

直接 k 次循环暴力显然会超时，所以不妨把 n 以内的所有质数预处理出来，然后 q 次询问 O(1) 的输出结果。观察数据范围，发现 n 的范围很大，O( n \sqrt{n} ) 的暴力筛显然会超时，所以考虑线性筛。

代码解析

外层循环枚举 i 从 2 到 n，如果此时 i 没被筛掉，那么他就是一个质数，直接加入质数表里。 如果 i 没有被认定为合数，那它一定是一个质数 然后内层枚举 j 从 1 到 coun（筛出的质数个数），也就是枚举所有筛出的质数，同时保证枚举范围不会越界。

is_pe[i*pe[j]]=1

上面的一行代码就是埃氏筛的思想的精髓——一个质数的倍数一定是一个合数，正确性显然。（不会这也要证明吧...）

if(i%pe[j]==0){break;}

这个的意思是如果 i 是 pe[j] 的倍数，那么此时 pe[j] 就是 i 的最小质因子，跳出循环，因为继续下去的话只会重复导致冗余，它的作用十分明显，见下面两条提交记录（看右上角的运行时间，快了三秒）

加了

没加

证明

复杂度证明：

空间复杂度：

显然是 O( n ) 的。

时间复杂度：

外层循环显然是 O( n ) 的，内层循环乍一眼可能会以为是嵌套的，但实际当一个数被他的最小质因子筛掉后就不会被重复筛掉了，所以也只会进行 n 次，所以整体复杂度是 O( n ) 的，可以通过此题。

正确性证明：

假设数 x 是合数，那么他一定可以表示成 k \times p 的形式，其中 p 是 x 的最小质因子，所以显然 p \le k ，一定会在 i 循环中被先扫到并把它的倍数也就是 x 筛掉，这样也就保证了每个合数都被筛掉。

结语

这是一道不错的模板题，它的思想对于其他类似问题很重要，拓展性强，能变形推出很多不同的算法和定理，强烈建议新手深刻理解并背下来。

日志：

2025/5/7/16:00完成，终于考完期中考试了。

2025/5/8/14/15打回第一次：“【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格。”

未完待续。