CSP-J 2024 第一轮 第 20 题：程序（一）：把判断上界改成 i<=n 后输入10的结果

题目

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

int sumPrimes(int n) {
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int x;
    cin >> x;
    cout << countPrimes(x) << " " << sumPrimes(x) << endl;
    return 0;
}

如果将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 $10$ 时，程序的输出（  ）。

选项

• A. 将不能正确计算 $10$ 以内素数个数及其和
• B. 仍然输出 $4$ 和 $17$
• C. 输出 $3$ 和 $10$
• D. 输出结果不变，但运行时间更短

答案

A

题解

选 A，修改后实际输出为：

``text 0 0 ``

关键在于：任何大于等于 2 的整数，都能被自身整除。

把循环条件改成 i <= n 后：

• 如果 n 是合数，会在找到因数时返回 false。
• 如果 n 是素数，循环会执行到 i == n，此时 n % i == 0，也会返回 false。

例如判断 2 时，第一次循环就有 2 % 2 == 0，于是连 2 都被判定为非素数。

因此，2～10 中所有数的判断结果都是 false，素数个数和总和都为 0。

原来的 i * i <= n 只检查不超过 $\sqrt n$ 的因数：如果一个数是合数，它必然有一个不超过 $\sqrt n$ 的因数，因此这样检查就足够了。