CSP-J 入门级 · CSP 2024 入门级第一轮 第 16 题

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第 1 题

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

判断题

1. 当输入为 $10$ 时，程序的第一个输出为 $4$ ，第二个输出为 $17$。（） 2. 若将 isPrime(i) 函数中的条件改为 i<=n/2，输入 $20$ 时， countPrimes(20) 的输出将

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心就是理解素数判断算法的边界条件和循环效率。拿到题先跑一遍代码看输入10时的素数2,3,5,7，再想命题人改循环条件是想考你对‘因子成对出现’和‘最大因子一定小于等于n/2’这两个性质的理解，别被表面改动迷惑。

判断题2最容易掉坑：把i*i<=n改成i<=n/2，很多人觉得循环多慢但结果变，其实只要n>4，n/2一定大于√n，条件i<=n/2依然能覆盖所有可能的因子，素数判断逻辑完全没变，20以内还是8个素数。单选题4里，改i<=n会让每个数都被自己整除判定为合数，导致输出全0，别误选‘运行时间更短’这种干扰项。

考点与概念

程序围绕‘素数判断’展开，核心函数isPrime(n)用试除法：从2遍历到√n，若发现能整除则非素数，否则为素数。countPrimes和sumPrimes分别统计和累加2到n范围内的素数。命题人喜欢在循环边界上做文章，考察你是否真正理解‘试除只需到√n’以及‘任何合数必有一个≤n/2的因子’这两个数论性质。

命题视角与思考心法

拿到题先手动模拟输入10：2,3,5,7四个素数，和为17，判断题1显然正确。接着看判断题2，命题人把i*i<=n改成i<=n/2，表面看循环次数增加，但你要想：一个数如果有因子，成对出现，最大的那个一定≤n/2（除非n是质数，此时没有真因子）。所以改条件后，对于任何n>4，依然能正确识别所有素数。20以内素数仍是8个，输出不会变，判断题2错误。单选题4更狠，把上限直接拉到n，那每个数i都会满足i<=i，且i%i==0，isPrime(i)全返回false，count和sum都成0，别被‘运行时间更短’这种选项带偏。