C++区间质数筛选（2种⽅法）
引⼦：Question:
给定两个数min,max，求出[min,max]区间的所有素数
C++的区间质数筛选，有两种⽅法。
Eratosthenes Algorithm
第⼀种就是Eratosthenes算法，该算法基于⼀个思想：对于任意的整数x，2x,⼀定不是质数。那好以⼆为起始点，很容易写出⼀下代码：
Code(Eratosthenes-1)
#include<cstdio>
#include<cstring>
bool vis[32768];
int main(){
int min,max;
scanf("%d %d",&min,&max);
memset(vis,1,sizeof(vis));
vis[1]=0,vis[0]=0;
for(int i=2;i<=max;i++){
if(vis[i]){
if(i>=min){
printf("%d ",i);
}
}
for(int j=i;j<=max;j+=i){
vis[j]=0;
}
}
return 0;
}
我再给⼀张图，来解释它的运算过程：
我们会发现j可以从i*i开始也不会影响结果。观察发现⽐i*i⼩的数在之前能够保证已经筛去了。这样可以减少不必要的冗余计算（重复标记）
Code(Eratosthenes-2)
#include<cstdio>
#include<cstring>
bool vis[32768];
int main(){
int min,max;
scanf("%d %d",&min,&max);
memset(vis,1,sizeof(vis));
vis[1]=0,vis[0]=0;
for(int i=2;i<=max;i++){
if(vis[i]){
if(i>=min){
printf("%d ",i);
}
}
for(int j=i*i;j<=max;j+=i){
vis[j]=0;
}
}
return 0;
}
时间复杂度：O（N log log N）
但即使这样，也⽆法避免重复计算！
如12被标记了两次，3*4与2*6。所以说，避免冗余运算是提⾼算法运算效率的关键，那么有没有这样⼀种完美的算法呢？有，那就是线性筛法！
线性筛法 Algorithm
先上代码：
Code(线性筛法)
#include<cstdio>
#include<cstring>
int vis[32768];
int prime[32768];
int main(){
int min,max;
scanf("%d %d",&min,&max);
memset(vis,0,sizeof(vis));
int tot=0;
for(int i=2;i<=max;i++){
if(vis[i]==0){
prime[++tot]=i;
vis[i]=i;
}
for(int x=1;x<=tot;x++){
if(prime[x]*i>max || prime[x]>vis[i])break;
vis[prime[x]*i]=prime[x];
}
}
for(int i=1;i<=tot;i++){
if(prime[i]>=min){
printf("%d ",prime[i]);
}
}
return 0;
}
我们从本质上思考重复计算的原因，发现我们对于同⼀个数的计算⽅式不同。那么怎样才能确定⼀个唯cstring转为int
⼀的计算⽅式呢？关键是质因⼦，因为每⼀个⼤于1的正整数都能分解为若⼲个质数的乘积。给⼀张图启迪你⼀下：
这样时间复杂度降到了O(N) 撒花，完结。。。
End~~~
谢谢⽀持，欢迎评论留⾔。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。