小明因为没做作业而被数学老师罚站,之后数学老师要他回家把第 n 个质数找出来。
小明于是交给聪明的你。请你帮忙!【wikioi-1530】
………………………… 以上为背景…………………………
老师怀疑小明仅仅是找到第 n 个质数,于是又叫小明把 1 到 n 以内(不包括 n)的质数全部找出来。小明又找到了你……
一个正整数 n。
(1<=n<=1000000)
n 以内的质数,每个一行。
233
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229 //(不含 n=233)
注意优化算法
淼!!
代码:
- #include < cstdio > #include < cstring > #include < cstdlib > #include < iostream > #include < algorithm > using namespace std;
- int n,
- ans,
- sum,
- tot;
- int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- while (ch >= '0' && ch <= '9') {
- x = x * 10 + ch - '0';
- ch = getchar();
- }
- return x * f;
- }
- bool pd(int x) {
- if (x == 1) return false;
- for (int j = 2; j * j <= x; j++) if (x % j == 0) return false;
- return true;
- }
- int main() {
- n = read();
- if (n > 1) printf("2\n");
- for (int i = 1; i < n; i += 2) {
- if (pd(i)) printf("%d\n", i);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2251094.html