GESP 五级第 02 讲：素数、筛法与唯一分解定理

本讲定位：初等数论的后半部分，也是五级真题的固定考点。2026 年 3 月五级判断题第 6 题就直接考唯一分解定理与判素数的关系。埃氏筛和线性筛是官方大纲逐字点名的两个算法，必须都会写。

对应官方大纲：五级知识块 1「初等数论」后半——素数与合数、质因数分解、唯一分解定理、素数表的埃氏筛法和线性筛法。

前置知识：五级第 01 讲（整除、约数、gcd）。

代码说明：本讲代码均已用 g++ 11.5（-std=c++11）编译运行验证，所有筛法结果、计数、耗时均为本机实测。

1. 素数与合数

1.1 定义（注意边界）

素数（质数）：大于 1 的整数中，除了 1 和它本身外没有其他约数的数。合数：大于 1 且不是素数的数。

$$ \boxed{1 \text{ 既不是素数，也不是合数}} $$

⚠️ 这是判断题的头号送分题，也是学生写代码时的头号 bug 来源（忘记特判 1）。

顺带记住：2 是唯一的偶素数，也是最小的素数。

前几个素数：$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$

实测：$1 \sim 100$ 有 25 个素数，$1 \sim 10^6$ 有 78498 个素数。（这两个数字值得让学生记一下，可用来自查筛法写得对不对。）

2. 判断单个数是否为素数

2.1 朴素做法与优化

// ❌ 朴素：O(n)
bool isPrime_slow(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;
    return true;
}

// ✅ 试除法：O(√n)
bool isPrime(int n) {
    if (n < 2) return false;                    // ⚠️ 1 和负数不是素数
    for (int i = 2; (long long)i * i <= n; i++) // 只枚举到 √n
        if (n % i == 0) return false;
    return true;
}

2.2 为什么枚举到 $\sqrt{n}$ 就够——攻克真题第 6 题

2026 年 3 月五级判断题第 6 题（题意）：

根据唯一分解定理，如果大于 1 的 $n$ 不被任何不超过 $\sqrt{n}$ 的质数整除，则 $n$ 是质数。

答案：✅ 正确。 但学生必须能证明，而不是背结论。

证明（反证法）：假设 $n > 1$ 且 $n$ 不被任何 $\le \sqrt{n}$ 的质数整除，但 $n$ 是合数。