筛素数的三种方法

前言：

一道数学题，最难想的小奥部分做对了，最后败在了筛素数（用了最质朴的方法
食用须知：文字解释较少，内容全面，仅作复习/归纳，时间充裕的初学者谨慎食用

---

Q：求n以内的素数

A：

1.朴素

• 思路：判断每一个数是否质数

• 时间复杂度：O(nsqrt(n))

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[10005];
bool judge(int x)
{
	if(x==1) return 0;
	if(x==2) return 1;
	for(int j=2;j*j<=x;++j){if(x%j==0) return 0;}
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		if(judge(i)) keep[++cnt]=i;
	printf("%d
",cnt);
	for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
	return 0;
}

---

2.埃氏筛法

• 思路：每筛出一个质数，就标记n以内此素数的倍数不能选

• 时间复杂度：O(nloglogn)

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[100005],temp[100005];
void sieve(int x)
{
	temp[0]=temp[1]=1;
	for(int i=2;i<=x;++i)
		if(!temp[i])
		{
			keep[++cnt]=i;
			for(int j=i+i;j<=x;j+=i) temp[j]=1;
		}
}
int main()
{
	scanf("%d",&n);
	sieve(n);
	printf("%d
",cnt);
	for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
	return 0;
}

---

3.欧拉筛法

• 思路：和2.埃氏筛法略有相似；任何合数都能表示成多个素数的积，枚举最小质因子之积从而标记不可选的数

• 时间复杂度：o(n)

• 代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt,keep[100005],vis[100005];
void sieve(int x)
{
	for(int i=2;i<=x;++i)
	{
		if(!vis[i]) keep[++cnt]=i;
		for(int j=1;j<=cnt,i*keep[j]<=x;++j)
		{
			vis[i*keep[j]]=1;//不能与下一句调换位置
			if(i%keep[j]==0) break;//当i是keep[j]的整数倍时（i%keep[j] == 0），i*keep[j+1]肯定被筛过，跳出循环
		}
	}
}
int main()
{
	scanf("%d",&n);
	sieve(n);
	printf("%d
",cnt);
	for(int i=1;i<=cnt;++i) printf("%d ",keep[i]);
	return 0;
}

---

后记：

• 筛素数是一项必备工具
• 朴素做法是必须写会的
• 后两种思想相似，思维方向不同
• 感性理解欧拉筛法