1013. 数素数 (20)

发表于 | 分类于 ，

题目描述

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

输入格式：

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

输出格式：

输出从P~M~到P~N~的所有素数，每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
#include <cstdio>
#include <vector>
using namespace std;

bool isPrime(int num, vector<int> &prime) {
    for (int i = 0; i < prime.size(); i++) {
        if (num % prime[i] == 0)
            return false;
    }
    return true;
}

int main()
{
    int m, n;
    int i, j;
    vector<int> prime;

    scanf("%d %d", &m, &n);
    prime.push_back(2);
    for (i = 3; prime.size() <= n; i++)
        if (isPrime(i, prime))
            prime.push_back(i);
    for (i = m - 1; i < n; i++)
        if ((i - m + 2) % 10 == 0 || i == n -1) {
            printf("%d\n", prime[i]);
        } else {
            printf("%d ", prime[i]);
        }

    return 0;
}

个人思考

这里有一个容易出错的地方是，PN代表的是第N个素数，如果使用筛法来判断的话，N不是边界条件，数组的上限也不容易判断。