Day 07　整除、质数与最大公约数

建议用时：25～30 分钟。请先打开今日知识卡完成复习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

复习目标：看清整除关系的方向，掌握质数判定、筛法、因数个数、最大公约数和最小公倍数，并能跟踪欧几里得算法中的变量变化。

今日练习

1. 【CSP-J 2023·第 7 题】以下关于高精度运算的说法错误的是（　）。

{{ select(1) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
• 大整数除以小整数的处理步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• 高精度加法运算的关键在于逐位相加并处理进位。

第 2～6 题共用程序

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

2. 【CSP-J 2024·第 16 题】当输入为 10 时，程序的第一个输出为 4，第二个输出为 17。（判断对错）

{{ select(2) }}

• 正确
• 错误

3. 【CSP-J 2024·第 17 题】若将 isPrime 函数中的循环条件改为 i <= n / 2，输入 20 时，countPrimes(20) 的输出将变为 6。（判断对错）

{{ select(3) }}

• 正确
• 错误

4. 【CSP-J 2024·第 18 题】sumPrimes 函数计算的是从 2 到 $n$ 之间的所有质数之和。（判断对错）

{{ select(4) }}

• 正确
• 错误

5. 【CSP-J 2024·第 19 题】当输入为 50 时，sumPrimes(50) 的输出为（　）。

{{ select(5) }}

• 1060
• 328
• 381
• 275

6. 【CSP-J 2024·第 20 题】如果将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 10 时，程序的输出（　）。

{{ select(6) }}

• 将不能正确计算 10 以内质数的个数及其和
• 仍然输出 4 和 17
• 输出 3 和 10
• 输出结果不变，但运行时间更短

7. 【数论巩固】$\gcd(84,126)$ 的值是（　）。

{{ select(7) }}

• 14
• 21
• 42
• 63

8. 【数论巩固】$\operatorname{lcm}(18,30)$ 的值是（　）。

{{ select(8) }}

• 60
• 90
• 120
• 180

9. 【数论巩固】正整数 72 一共有多少个正因数？（　）

{{ select(9) }}

• 8
• 10
• 12
• 14