PAT 乙级 1013. 数素数 (20) C++版

Posted on Edited on In

令Pi表示第i个素数。现任给两个正整数M <= N <= 104，请输出PM到PN的所有素数。

输入格式：

输入在一行中给出M和N，其间以空格分隔。

输出格式：

输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int prime[1000000];

inline void getPrime() {

    int m = 1000;
    int i, j;

    for (i = 2; i < 1000; i++) {
        if (!prime[i]) {
            for (j = i * i; j < 1000000; j += i)
                prime[j] = 1;
        }
    }
    j = 0;
    for (i = 2; i < 1000000; i++)
        if (!prime[i])
            prime[j++] = i;
}


int main() {
    memset(prime, 0, sizeof(prime));
    int num = 0;
    bool flag = false;
    int M, N;
    getPrime();
    cin >> M >> N;

    for (int i = M - 1; i < N; i++) {
        if (num != 0 && num % 10 == 0) {
            cout << endl;
            flag = false;
        }
        if (flag)
            cout << " ";
        else
            flag = true;
        cout << prime[i];
        num++;
    }

    return 0;
}