AcWing 868. 筛质数
原题链接
简单
作者:
术
,
2021-01-31 13:07:39
,
所有人可见
,
阅读 301
1埃氏筛法
#include <iostream>
using namespace std;
const int N=1000005;
bool st[N];
int primes[N];
int main()
{
int n;
cin>>n;
int cnt=0;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i) st[j]=true;
}
}
cout<<cnt;
//cout << "Hello world!" << endl;
return 0;
}
2线性筛法
#include <iostream>
using namespace std;
const int N=1000005;
bool st[N];
int primes[N];
int main()
{
int n;
cin>>n;
int cnt=0;
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++) {
st[primes[j]*i]=true;
if(primes[j]%i==0) break;
}
}
cout<<cnt;
//cout << "Hello world!" << endl;
return 0;
}