模板 埃式筛法
作者:
lrx2020
,
2023-02-01 14:32:17
,
所有人可见
,
阅读 270
模板 埃式筛法
#include <iostream>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
const int N = 1e9+10;
bool v[N];
vector<int> s;
vector<int>::iterator it;
void prime(int n){
memset(v,0,sizeof v);
for(int i=2;i<=n;i++){
if(v[i]) continue;
s.push_back(i);
for(int j=i;j<=n/i;j++) v[i*j] = 1;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("result.out","w",stdout);
int n;
cin >> n;
prime(n);
for(it=s.begin();it!=s.end();it++) cout << *it << " ";
return 0;
}