AcWing 868. 筛质数
原题链接
简单
作者:
墨白
,
2021-02-09 14:38:40
,
所有人可见
,
阅读 326
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
bool st[N];
int prime[N],cnt;
//埃氏筛法
void prime_number(int n){
for(int i = 2;i <= n;++i){
if(!st[i]){
st[i] = true;
for(int j = i + i;j <= n;j += i){
st[j] = true;
}
prime[cnt++] = i;
}
}
}
//线性筛法
void prime_number1(int n){
for(int i = 2;i <= n;++i){
if(!st[i]) prime[cnt++] = i;
for(int j = 0;prime[j] <= n / i;++j){
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
int main(){
int n;
cin >> n;
prime_number(n);
cout << cnt << endl;
return 0;
}