AcWing 3526. 素数
原题链接
简单
作者:
MeowRain
,
2024-02-16 13:09:29
,
所有人可见
,
阅读 30
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int prime[N],st[N];
int cnt;
void get_prime(int n) {
for(int i = 2;i<=n;i++) {
if(!st[i]) {
prime[cnt++] = i;
}
for(int j = 0;prime[j] <= n/i && j <= cnt;j++) {
st[i*prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
void get_prime2(int n) {
for(int i = 2;i<=n;i++) {
if(!st[i]) prime[cnt++] = i;
for(int j = i;j<=n;j+=i){
st[j] = true;
}
}
}
int main() {
int n;
while(cin >> n) {
memset(prime,0,sizeof(prime));
memset(st,0,sizeof(prime));
cnt = 0;
get_prime(n - 1);
bool flag = false;
for(int i = 0;i<cnt;i++) {
if(prime[i] % 10 == 1) {
flag = true;
cout << prime[i] << " ";
}
}
if(!flag) cout << -1;
cout << endl;
}
}