Skip to content

数素数

题目链接

时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB

题目描述

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

输入描述:

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

输出描述:

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

输入例子:

5 27

输出例子:

11 13 17 19 23 29 31 37 41 4347 53 59 61 67 71 73 79 83 8997 101 103

源码:

#include <iostream>
using namespace std;
int main() {
    int M, N;
    int primeCounter = 0;
    int printedCounter = 0;
    cin >> M >> N;
    bool isPrime;
    for (int i = 2; true; i++) {
        isPrime = true;
        for (int j = 2; j <= i / j; j++) {
            if (0 == i % j) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primeCounter++;
            if (primeCounter < M) continue;
            cout << i;
            if (primeCounter == N) break;
            printedCounter++;
            if (0 == printedCounter % 10) cout << endl;
            else cout << ' ';
        }
    }
    return 0;
}

错误示例:

#include <iostream>
using namespace std;
int main() {
    int M, N;
    int primeCounter = 0;
    int printedCounter = 0;
    cin >> M >> N;
    bool isPrime;
    for (int i = 2; i < 9998; i++) {  // i < 9998 对素数的边界估计错误  Debug: 把 i < 9998 改为 true
        isPrime = true;
        for (int j = 2; j <= i / j; j++) {
            if (0 == i % j) {
                isPrime = false;
                break;
            }
            else continue;
        }
        if (isPrime) {
            primeCounter++;
            if (primeCounter < M) continue;
            // 以下 1 和 2 的顺序会导致最后一行末尾有多余的空格
            // Debug: 先把把 1 和 2 顺序倒过来,再把primeCounter > N 改为 primeCounter == N
            if (primeCounter > N) break;  // 1
            cout << i;  // 2
            printedCounter++;
            if (0 == printedCounter % 10) cout << endl;
            else cout << ' ';
        }
    }
    return 0;
}

拓展阅读:

素数计数函数