C++计算质数--欧拉筛和埃氏筛原理学习

60 阅读 0 评论 40 点赞

我是靠谱客的博主彪壮苗条，最近开发中收集的这篇文章主要介绍C++计算质数--欧拉筛和埃氏筛原理学习，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

质数简单来说就是除了1和自身之外其他再无公因数的正整数，如2,3,5,7。2是最小的质数。
有一些常见的题都要求先筛出一定范围内的所有质数（或者是合数），如筛选出1-n中所有的质数。所以欧拉筛和埃氏筛成为了常用工具。

TIPS：本文所有观点，可能有些偏差，只是本人初学之后所有感悟，有错误之处，希望能及时指出。

埃氏筛

首先先说一下埃氏筛的运作。
埃氏筛比较简单易理解。
题目：要求得到小于等于n的所有质数的数量
第一层循环，从1遍历到sqrt(n)的所有数，然后对于每一个数再从2倍开始枚举，将所得到的倍数记录为合数，除去合数，剩下的全部为素数。

int countPrimes(int n){
//排除特殊情况
if (n <= 2)
{
return 0;
}
//res为素数（质数）的数目
int res = n - 2;
//s为记录该数是不是素数，初始默认全为素数
vector<bool> s(n);
for (int i = 2; i <= sqrt(n); ++i)
{
if (!s[i])//如果是素数
{
for (int j = 2; i * j < n; ++j)//枚举该素数的所有倍数
{
if(!s[i*j])//如果未被标记过
{
s[i * j] = true;//记录为合数
--res;//素数的数目-1
}
}
}
}
return res;

这里只解释一点，为什么在第二层循环中，if判断成为了未被标记过，因为是从小到大进行枚举，所以如果在枚举倍数时发现了一个s[i*j]为false的值，说明该数是没有遍历过的，一定为合数。

那么为什么不直接s[ij]=true,–res呢？*
因为有可能出现这样的特例。
如15是素数3和5的公倍数，在枚举3的倍数的时候就剔除掉15了，在枚举5的倍数的时候又遍历到了15，若不进行if判断，则会导致res减2（实际应该只减1，因为只剔除掉了15这一个数），会造成重复筛选，导致答案偏小。

时间复杂度：
很明显，时间复杂度是O(n*logn)级别的，其实已经比较优秀了。

但是有没有一种更优秀的筛选方法可以做到线性O（n）级别的筛选呢？
分析埃氏筛，我们发现有一个地方会导致很多重复，那就是对于同一个公倍数，需要筛选好几遍，比如说之前所举例子中的15，会被遍历两遍，如果这个数很大，同时是好几个质数的倍数呢？那么会大大增加复杂度，所以从这一小点入手，可以进行升级改造！

欧拉筛

接下来介绍一下欧拉筛（线性筛），它的时间复杂度为O（n）级别的
有了前面所说，我们先上代码，再说。

	//本代码引用自其他博主
//原文链接：
//https://blog.csdn.net/TheWayForDream/article/details/109060845
int n;
memset(prime,0,sizeof(prime));
memset(vis,false,sizeof(vis));
cin >> n;
vis[1]=true;
for(int i=2;i<=n;++i)
{
if(!vis[i])//这个数没有遍历过，说明不是其他数的倍数，是素数
{
vis[i]=true;//已遍历过
++prime[0];//素数数+1
prime[prime[0]]=i;//将此素数按顺序记录下来
}
//遍历每个素数，并且以当前遍历到的i为倍数，去与各素数相乘
//得到i*j为对应的素数的倍数
for(int j=1;j<=prime[0] && (i*prime[j])<=n;++j)
{
//标记遍历过这个数了，且prime[j]*i为倍数
//不会再遍历到了
vis[prime[j]*i]=true;
//如果当前i是这个素数的倍数，则无需再向后看，直接break掉
if(i % prime[j]==0)
{
break;
}
}
}
cout<< prime[0];//质数的数目
return 0;

重点解释几点。
prime数组是按顺序记录所有出现过的质数，其中prime[1]为特殊位，其数字代表当前所遍历到的位置之前有多少个质数。
vis数组是记录每个数是否已经到达过了，与埃氏筛中作用相近。

讲一下二重循环中的
if (i % prime[j] == 0) 这个判断。
我们要优化掉埃氏筛中的重复，这是关键一步。
假设i == prime[j] * t，那么我们这样会直接break掉循环，要做到不重不漏才能保证正确性。
不重： 假设后面还有 i % prime[j + x] == 0
那么就有 i * prime[ j + x]==prime[j] * t * prime[j + x]，相当于是prime[ j ]的倍数，不需要重复再进行筛选。
不漏：
①会出现素数错认为为合数吗？
不会，如果该数为素数，则永远不会成为某个数的倍数，一定会在第一重循环中的if判断中被检测出来。
②会出现合数错认为为质数吗？
不会，若该数为合数，则一定是某个更小的素数的倍数，则一定会在二重循环中被检测出来，从而剔除掉。

时间复杂度：
首先在欧拉筛中对于每一个数，最多访问的次数就是1次，不会出现埃氏筛中同一个数多次访问的情况，用一个判断就可以解决了这个问题，所以复杂度为O（n）