AcWing 868. 筛质数
原题链接
简单
作者:
xybh
,
2020-11-21 20:21:00
,
所有人可见
,
阅读 438
埃氏筛
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
bool is[N];
void init(int n){
memset(is, 1, sizeof is);
is[0] = false; is[1] = false;
for(int i = 2; i <= n; i++){
if(is[i]){
for(int j = 2 * i; j <= n; j += i){
is[j] = false;
}
}
}
}
int main(){
int n, ans = 0;
cin >> n;
init(n);
for(int i = 1; i <= n; i++){
if(is[i]) {
ans++;
}
}
cout << ans;
return 0;
}
线性筛
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
bool is[N];
int prime[N], cnt;
void init(int n){
for(int i = 2; i <= n; i++){
if(!is[i]) prime[cnt++] = i;
for(int j = 0; prime[j] <= n / i; j++) {
is[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
int main(){
int n;
cin >> n;
init(n);
cout << cnt;
return 0;
}