AcWing 868. 筛质数
原题链接
简单
作者:
古娜拉黑暗之神
,
2021-05-13 17:40:51
,
所有人可见
,
阅读 294
埃氏筛法
//筛质数法 埃及筛法
#include <iostream>
using namespace std;
const int N = 1000000;
int primes[N],k;
bool st[N];//默认都是素数
int n;
void is_prime(int n){
for(int i=2;i<=n;i++){
if(st[i]){//是素数
primes[k++]=i;
for(int j=i+i;j<=n;j=j+i) st[j]=false;//然后把这个素数的所有倍数删除
}
}
}
void show_prime(){
for(int ll=2;ll<=n;ll++){
if(st[ll]==true){
cout<< ll << " ";
}
}
cout << endl;
}
int main(){
cin >> n;
for(int i=0;i<N;i++){
st[i]=1;
}
is_prime(n);
//show_prime();//可以显示具体哪些是质数
cout << k<< endl;
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH