算法笔记--素数筛（朴素筛，埃式筛，欧拉筛）_素数筛子

素数

素数也叫质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。如2 , 3 , 5 , 7 , 11等。

素数筛

素数筛即筛选出1~n内的素数的方法，这里介绍三种

1.朴素筛

由上面的概念得，我们可以想到引入一个从1到它本身的for循环，只要中间有取余为0，那么它就不是素数。

#define MAX 100000
int prime[MAX];
int x=0;
void psshai(int n)
{
	for(int i=2;i<=n;i++)//因为1不是素数，从2开始遍历
	{	
		int flag=0;//标记为0，假设该数是素数
		for(int j=2;j<i;j++)//取2~i-1判断（优化一下：i也可以换成根号i，但这样只稍微增加了一点速度）
		{
			if(i%j==0)//取余为0，该数不是素数
			{
				flag=1;//标记解除
				break;
			}
		}
		if(flag==0)//标记未解除，说明该数是素数
			prime[++x]=i;//存储
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这种算法就是暴力枚举，优化后时间复杂度O(n*sqrt(n))。不推荐，太慢。

2.埃氏筛

我们知道最小的素数是2，埃氏筛就是从2开始，在判断该数是否为素数的同时将该数的倍数筛去，因为一个数（从2开始）的倍数一定不是素数，注意一下范围别超过n就行

#define MAX 100000
bool Isprime[MAX];
void asshai(int n)
{
	for(int i=2;i<=n;i++)
		Isprime[i]=true;//初始化2~n都是素数
	for(int i=2;i<=n;i++)//遍历
	{
		if(Isprime[i])//如果是素数
		{
			for(int j=2;i*j<=n;j++)//把是i的j倍的数都去掉，注意范围到n
			{
				Isprime[i*j]=false;
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这种算法的时间复杂度是O(nlogn)，但是我们会发现里面的一些操作有点冗余。比如数字6，它既是2的3倍又是3的2倍，这样在筛选的时候被筛出去两次，其实是在重复的做无用功。即使这样，这种算法一般的题也能用

3.欧拉筛

欧拉筛就是对埃氏筛的优化了，即使一个数仅被一次筛除

#define MAX 100000
bool vis[MAX];//默认都是false
int prime[MAX];
int x=0;
void olshai(int n)
{
	for(int i=2;i<=n;i++)
		vis[i]=true;//初始化2~n都是素数
	for(int i=2;i<=n;i++)
	{
		if(vis[i])//如果是素数
			prime[++x]=i;//存储在prime中
		for(int j=1;j<=x && i*prime[j]<=n;j++)//核心部分，下文详细讲
		{
			vis[i*prime[j]]=false;
			if(i%prime[j]==0)
				break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1、当 i 是素数时，存储素数，并剔除 i 的整数倍，其中整数应为素数且小于等于前 i 个数中已知最大的素数，注意乘积小于等于n
2、当 i 不为素数，剔除 i 的整数倍，在注意上面（其中整数应为素数且小于等于前 i 个数中已知最大的素数，注意乘积小于等于n）要求的同时判断 i % prime[j]，如果整除则退出
i % prime[j]这一步就是对埃氏筛的优化，举个例子理解一下
如果没有这一步，那么当i=9时，prime【1】=2，prime【2】=3，prime【3】=5，prime【4】=7；本来是当 j=2 的时候跳出循环，但是却没有，那么j = 3时 9 * 5 =45，该统计在 i = 15 的时候也会统计，也就是当 i = 15 时候，j = 2 ，prime【2】 = 3，也统计了 3 * 15 = 45 ，明显，重复统计，所以要及时break。
欧拉筛的时间复杂度是O(n),所以普遍使用欧拉筛来筛选素数

---

当然如果区间非常非常大的时候，就要用到区间筛用偏移来筛选了，这种情况少见，就不多介绍了,感兴趣可以继续研究~~（本人能力有限）~~
本篇对这篇博客（写的很好，通俗易懂，点击查看哦）
有所借鉴。