素数3
2024-07-22 18:37:23
发布于：北京
5阅读
0回复
0点赞
#include<iostream>
using namespace std;
const int maxn=1e8+9;
bool vis[maxn];
int prime[maxn];
void Init(int n){
vis[0]=vis[1]=true;//vis[0],vis[1] 单独处理
int lp=0;//素数个数
}
int main(){
int n;
cin>>n;
vis[0]=vis[1]=true;
int lp=0;
for(int i=2;i<=n;i++){//从2开始删
if(!vis[i]){//找到素数
prime[lp]=i;//存入素数数组
}
for(int j=1;j<=lp;j){//筛去当前i与素数数组元素的积
if(1LLiprime[j]>n){
break;//超出筛选范围
}
vis[i*prime[j]]=true;//筛掉背书
if(i%prime[j]==0){
break;//后面的数字都能比i更大的数字筛掉
}
}
}
cout<<lp<<endl;
return 0;
}
这里空空如也
有帮助，赞一个