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

一些闲话

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

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

ACcode：

CPP

#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

（筛出的质数个数），也就是枚举所有筛出的质数，同时保证枚举范围不会越界。

CPP

is_pe[i*pe[j]]=1

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

CPP

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打回第一次：“【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格。”

未完待续。

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

文章操作

一些闲话

ACcode：

算法介绍

思路：

代码解析

证明

复杂度证明：

空间复杂度：

时间复杂度：

正确性证明：

结语

相关推荐

评论

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