数素数 (PATB-1013)
题面
令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤10^4，请输出 PM 到 PN 的所有素数。
输入
输入在一行中给出 M 和 N，其间以空格分隔。
输出
输出从 PM 到 PN 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。
样例输入
15 27样例输出
111 13 17 19 23 29 31 37 41 43
247 53 59 61 67 71 73 79 83 89
397 101 103提示
无
思路
代码
1const int mxn = 1e6 + 5;
2bool isP[mxn];
3int prime[mxn];
4
5int euler(int n)
6{
7 memset(isP, 1, sizeof isP);
8 isP[0] = isP[1] = 0;
9
10 int cnt = 0;
11 for (int i = 2; i <= n; i++)
12 {
13 if (isP[i]) prime[++cnt] = i;
14 for (int j = 1; j <= cnt; j++)
15 {
16 if (i * prime[j] > n) break;
17 isP[i * prime[j]] = 0;
18 if (i % prime[j] == 0) break;
19 }
20 }
21 return cnt;
22}
23
24int n, m;
25
26int main()
27{
28 int cnt = euler(N);
29 scanf("%d %d", &n, &m);
30
31 int nf = 0, lc = 0;
32 for (int i = n; i <= m; i++)
33 {
34 if (nf)
35 printf(" ");
36 else
37 nf = 1;
38
39 printf("%d", prime[i]);
40 lc++;
41
42 if (lc % 10 == 0)
43 {
44 nf = 0;
45 printf("\n");
46 }
47 }
48
49 return 0;
50}