-
Notifications
You must be signed in to change notification settings - Fork 104
/
6.8.cpp
58 lines (51 loc) · 1.46 KB
/
6.8.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
* 题目名称:素数
* 题目来源:北京航天航空大学复试上机题
* 题目链接:http://t.cn/AiCulqtW
* 代码作者:杨泽邦(炉灰)
*/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 10000 + 10;
vector<int> prime; //保存质数
bool isPrime[MAXN]; //标记数组
void Initial() {
for (int i = 0; i < MAXN; ++i) { //初始化
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i < MAXN; ++i) {
if (!isPrime[i]) { //非质数则跳过
continue;
}
prime.push_back(i);
if (i > MAXN / i) { //过大的数提前跳出
continue;
}
for (int j = i * i; j < MAXN; j += i) {
isPrime[j] = false; //质数的倍数为非质数
}
}
return ;
}
int main() {
Initial();
int n;
while (scanf("%d", &n) != EOF) {
bool isOutput = false; //判断是否有输出
for (int i = 0; i < prime.size() && prime[i] < n; ++i) {
if (prime[i] % 10 == 1) {
isOutput = true;
printf("%d ", prime[i]);
}
}
if (!isOutput) {
printf("-1");
}
printf("\n");
}
return 0;
}