初赛专题（十一）：数论与数学小算法 —— 质数、约数、gcd、平方数与模运算

本讲定位：CSP-J 初赛系列的数论专题。为什么单开一讲？因为七年真题统计（见 cspj-exam-analysis-2019-2025.md）里它是全卷第一大题材：2020 完善程序考质因数分解、2021 阅读程序整段考约数、2022 考枚举因数和求平方根、2023 考因子平方和、2024 考质数统计和完全平方数、2025 考 gcd 与互质枚举——每年至少一段程序题，折算 12~15 分，另有选择题不时加码。

初赛数论有两种考法，本讲每个知识点都按两种考法各练一遍：手算（选择题：97 是不是质数、gcd(319,377) 是多少）和读写代码（程序题：试除循环的边界、成对枚举防重复）。不涉及复赛的同余理论和逆元，全部内容都在入门级考纲内。

前置知识：整除与余数（% 运算符）、第 01 讲的 STL 基础。

适合对象：CSP-J 初赛。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。

1. 整除与质数

1.1 试除法判定质数

质数：大于 1、且只有 1 和自身两个约数的整数。判定 $n$ 是否为质数，不需要试除到 $n-1$，试除到 $\sqrt{n}$ 就够了——如果 $n = a \times b$ 且 $a \le b$，那么必有 $a \le \sqrt{n}$；既然找不到 $\le \sqrt{n}$ 的因子，也就不存在任何因子。

bool isPrime(int n) {
    if (n < 2) return false;          // 0、1 都不是质数——最常被忘掉的边界
    for (int i = 2; i * i <= n; i++)  // i*i <= n 等价于 i <= sqrt(n)，且避开浮点
        if (n % i == 0) return false;
    return true;
}

三个必须讲透的细节，全都是真题考过的：

循环条件写 i * i <= n 而不是 i <= sqrt(n)：避免浮点误差，也是程序题里的标准写法（2024 阅读程序原型）。
n < 2 的边界：判断题问”输入 1 时返回什么”，漏了这行就是送分给出题人。
复杂度是 $O(\sqrt{n})$：阅读程序的复杂度选择题常拿它出题。

选择题手算技巧：判定一个两位数/三位数是不是质数，只需用 $\le \sqrt{n}$ 的质数去试除。比如 97：$\sqrt{97} < 10$，试除 2、3、5、7 都不行——97 是质数。这正是 2019 年选择题”100 以内最大的素数”（答案 97）的做法。

顺手记住两个常考数字：100 以内质数有 25 个（2021 阅读程序把它藏在”$f[1..100]$ 中约数个数等于 2 的数有几个”里考）；1000 以内有 168 个（了解即可）。

1.2 例题一：统计质数（2024 阅读程序第 1 段原型）

2024 年阅读程序第 1 段就是”isPrime + 主循环统计 $2..n$ 的质数个数与总和”，考法是：给定输入验证输出、修改循环条件问结果变化、归纳函数功能。完整程序：

#include<iostream>
using namespace std;

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

int main() {
    int n, cnt = 0, sum = 0;
    cin >> n;
    for (int i = 2; i <= n; i++)
        if (isPrime(i)) { cnt++; sum += i; }
    cout << cnt << " " << sum << endl;
    return 0;
}

输入 100，输出 25 1060。读这类程序时在草稿纸上记下”cnt 数个数、sum 累加值”即可，不要逐个质数硬算——判断题考的是结构（边界、条件、复杂度），不是算术。

1.3 埃氏筛：一次筛出一批质数

要判定的数很多时，逐个试除太慢。埃拉托斯特尼筛反过来做：从 2 开始，每找到一个质数，就把它的所有倍数划掉：

const int N = 1000005;
bool composite[N];              // composite[i] 为 true 表示 i 被划掉（是合数）

void sieve(int n) {
    for (int i = 2; i <= n; i++)
        if (!composite[i])                       // i 没被划掉 → i 是质数
            for (int j = 2 * i; j <= n; j += i)  // 划掉 i 的所有倍数
                composite[j] = true;
}