Skykey's Home

Skykey的私人博客ᕕ( ᐛ )ᕗ

欧拉筛法

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

欧拉筛法

原创程画 最后发布于2018-05-15 18:24:08 阅读数 4146 收藏

想看欧拉筛法的可直接拉到最后。

相信各位对素数并不陌生，素数就是指不能被除了1和自身以外的别的数整除的数，比如2,3,5，而且根据欧几里得的证明来看，素数是无限的，普通的筛选素数的方法可能对较小的数据能在较短时间内完成筛选，但对于很大的数据（比如1e9）就会花费很长的时间。

1.普通的求素数方法

例如，普通的求素数方法时这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int pri[MAXN];
int cnt=0;
void prime(int n)
{
	cnt=0;
	pri[cnt++]=2;
	int i,j;
	for(i=3;i<=n;++i)
	{
		for(j=2;j<i;++j)
		{
			if(i%j!=0)
				break;
		}
		if(j>=i)
			pri[cnt++]=i;
	}
}


根据素数的定义所写的代码很容易理解，但是运行的效率是不太优秀的，所以我们要改进，当然在学习的过程中相信大家也或多或少的学了些改进方法，一个简单的改进方法就是将第二个循环的结束条件改为j<sqrt(i)，相应地再更改判断条件，这样当然可以减少我们运行所需要的时间，但是任然不够好，下面我们就来介绍一下埃式筛法和今天的真正目标——欧拉筛法。

2.埃式筛法

先来介绍埃式筛法，埃式筛法的基本思想就是，当我们遍历到一个素数时，把所有该素数的倍数（自然是合数）都筛选出来，我们来看看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int prime[MAXN];
bool vis[MAXN];
int cnt=0;
void Era_prime(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])
			prime[cnt++]=i;
		for(int j=i;j<=n;j+=i)
		{
			vis[j]=true;
		}
	}
}

当我们有没被选过的素数时，加入素数数组prime并且将它的所有n以内的倍数给筛选出来（vis[j]=true），埃式筛法很容易理解，并且在效率上也比较优秀，时间复杂度为O(nlglgn)，但是在处理1e8以上的数据时，还是稍稍力不从心，所以接下来我们着重介绍下线性时间筛法——欧拉筛法，我们还是先来看下代码：

3.欧拉筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int prime[MAXN];
bool vis[MAXN];
int cnt=0;
void Euler_prime(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])
		{prime[cnt++]=i;vis[i]=true;}//vis[i]置为true或不置true都可以
		for(int j=0;j<cnt;++j)
		{
			if(i*prime[j]>n)//判断是否越界
				break;
			vis[i*prime[j]]=true;//筛数
			if(i%prime[j]==0)//时间复杂度为O(n)的关键！
				break;
		}
	}
}

我们注意到，在用埃式筛法的同时，同一个数字也许会被筛选多次，比如6先被2筛选一次，再被3筛选一次，这样就浪费了很多不必要的时间，而欧拉筛法通过if(i%prime[j]==0)break;这一步就避免了重复筛选的发生，我们举个例子，比如，2先筛选了4，然后进行下一个循环，3筛选6和9，当我们执行到4的时候，可以发现，当i==4时，第一次运行到if(i%prime[j]==0)这一步的时候就直接break;掉了，这也就是说，当我们的合数进入循环时，其实它已经被之前的数筛选过了，所以当合数进入内层循环时，内层循环只执行了一次，从而减少了时间复杂度。

结束

————————————————
版权声明：本文为CSDN博主「程画」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/chczy1/java/article/details/80327323

相关文章