CSP-J 2024 第一轮 第 17 题：程序（一）：把判断条件改成 i<=n/2 是否会改变 countPrimes(2

题目

#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;
}

若将 isPrime(i) 函数中的条件改为 i<=n/2，输入 $20$ 时， countPrimes(20) 的输出将变为 $6$。（）

选项

• √. 正确
• ×. 错误

答案

×

题解

选 ×，错误。 修改后，countPrimes(20) 的结果仍然是 8。

把循环条件从 i * i <= n 改为 i <= n / 2，仍能正确判断质数：

• 合数一定有一个因数在 2 到 n / 2 之间，因此仍会返回 false。
• 质数在这个范围内没有因数，因此仍会返回 true。对于 2 和 3，循环不执行，直接返回 true，也正确。

不超过 20 的质数有： \[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19 \] 共 8 个。

因此，修改只是扩大了试除范围，可能增加计算量，不会把结果变成 6。