素数与合数

上一部分我们聚焦在整数之间的整除关系，弄清楚了一个数"能不能干净地量尽"另一个数，以及随之而来的因数计数与整除判别。那讲的是两个数之间的"关联"。今天我们换一个视角，把目光收回到每一个数本身，问一个更根本的问题：一个正整数，能不能被进一步"拆开"？这个问题听起来简单，但它引出了数学史上最深刻的研究领域之一，也是整个数论大厦的另一根主梁。

化学里，物质由原子构成，水分子是两个氢原子加一个氧原子，铁块是铁原子的堆积。正整数的乘法世界里存在完全类似的"原子"——那些最基础的、无法再被拆分的数，正是我们今天要认识的素数。而由它们组合拼出的那些数，就是合数。理解了素数，就理解了整数乘法意义下的原子论。

素数的定义

理解素数最直接的路径，是观察因数的个数。对于正整数 $6$，它的正因数是 $1, 2, 3, 6$，共四个；对于 $15$，正因数是 $1, 3, 5, 15$，共四个；对于 $7$，正因数仅有 $1$ 和 $7$ 本身，只有两个。$6$ 和 $15$ 都能被"额外"的因数整除，因此可以写成更小正整数的乘积（$6 = 2 \times 3$，$15 = 3 \times 5$）；而 $7$ 则不行，除了平凡的 $1 \times 7$ 之外，它无法再被拆开。因数只有这两个的数，就是素数。

这个定义有一个需要特别说明的边界情形：$1$ 既不是素数，也不是合数。$1$ 的正因数只有它自身，不满足素数"恰好有两个因数"的要求；同时它也没有"额外"因数，所以也不是合数。把 $1$ 单独排除，并非数学家的随意规定——稍后我们会看到，这是为了保证算术基本定理中"唯一分解"这一核心性质成立的必要前提，排除 $1$ 是逻辑上的必然，而非约定上的权宜。

最小的素数是 $2$，其次是 $3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$ 你一定注意到了一件有趣的事：除了 $2$，后面所有的素数都是奇数。这并不奇怪——任何大于 $2$ 的偶数都能被 整除，也就拥有了一个"额外因数" ，自然成了合数。 因此成了整个素数序列里唯一的偶数，数论中有时戏称它是"最孤独的素数"，因为在偶数阵营里，它是唯一的素数，而在奇数阵营里，它又不属于那里。

判断素数的方法

试除法：从最小因子入手

判断一个给定正整数 $n$ 是否为素数，最直接的方法是试除法：按顺序用 $2, 3, 4, \ldots$ 去除 $n$，看是否能整除。关键的效率改进是：试除只需进行到 $\sqrt{n}$ 为止。理由如下：若 且 ，则 ，即 ——也就是说， 的。因此，若在 到 的范围内找不到任何能整除 的数， 就是素数。

以 $n = 97$ 为例。由于 $\sqrt{97} \approx 9.8$，只需试除 $2, 3, 4, 5, 6, 7, 8, 9$：将 依次除以这些数，所有结果都不是整数，所以 是素数。进一步的效率优化是：试除时只需试素数而非所有整数，因为合数的因数里必然包含更小的素数，若 不能被那个更小的素数整除，也就不能被这个合数整除。对于 的情形，只需试 四个素数就已足够。

试除法在 $n$ 较小时非常实用，但当 $n$ 是天文数字量级的大数（例如现代密码学中使用的数百位整数）时，它的效率就远远不够了。那时需要更复杂的概率性素数检测算法，这是数论与计算机科学交叉的前沿地带，我们现阶段先掌握试除法即可。

埃拉托色尼筛法：批量寻找素数

如果目标不是判断单个数，而是找出某个范围 $[2, N]$ 内的所有素数，逐个试除的效率就太低了。公元前三世纪，古希腊数学家埃拉托色尼（Eratosthenes）发明了一种精妙的"筛子"，一口气滤去所有合数，留下纯净的素数。

筛法的思路极为朴素：从 $2$ 开始，将 $2$ 的所有倍数（$4, 6, 8, \ldots$）标记为合数，保留 $2$ 本身；接着找到下一个未被标记的数 $3$，并标记 $3$ 的所有倍数；如此循环，直到当前处理的素数 $p$ 满足 为止——此时所有未被标记的数都已经是素数。一个重要的优化细节是：对于素数 ，标记倍数时无须从 开始，因为 这些数已经在处理更小素数时被标记过了，只需从 开始标记，可以省去大量重复操作。

以找出 $30$ 以内所有素数为例。先列出 $2$ 到 $30$ 的所有整数；第一轮取 $p = 2$，从 $4$ 开始划去所有 $2$ 的倍数；第二轮取 $p = 3$，从 开始划去 （ 已被第一轮划去）；第三轮取 ，从 开始，仅需划去 ；由于 ，筛法终止。最终幸存的数是 ，共 个，这就是 以内的全部素数。

这个算法的理论时间复杂度是 $O(N \log \log N)$，远优于对每个数逐一试除的 $O(N\sqrt{N})$。埃拉托色尼的这张"筛子"已经沿用了两千余年，在现代计算机上处理千万量级的范围时依然是首选的基础算法。它能历久弥新的原因，在于它完全顺应了整除关系的结构——每个合数都被它的最小素因子"揭发"，没有任何合数能漏网。

算术基本定理

素数之所以被称为整数世界的"原子"，是因为下面这条定理保证了每个大于 $1$ 的正整数都能被素数唯一地"拼出来"。

这个定理包含两个层次的断言，缺一不可。其一是存在性：任何大于 $1$ 的正整数都有素数分解。其二是唯一性：这个分解在忽略排列顺序的意义下是唯一的，不存在两种本质不同的写法。几个直观的例子是 $12 = 2^2 \times 3$，$60 = 2^2 \times 3 \times 5$，，。对每一个你熟悉的数，试着找它的素因数分解，系统的写法是把素数因子从小到大排列并写出各自的指数，这样就得到了唯一确定的"身份证"。

存在性的证明依赖良序原理：若某个大于 $1$ 的正整数没有素因数分解，取所有这样的数中最小的一个，设为 $m$。$m$ 本身如果是素数，那 $m = m^1$ 就是平凡的素数分解，矛盾；若 $m$ 是合数，则 $m = a \times b$，其中 ，由 的最小性， 和 都有素因数分解，把它们合并就得到 的素因数分解，也形成矛盾。因此不存在"无法分解"的整数，存在性得证。唯一性的证明则需要一条关键引理——素数的整除性质（如果素数 整除乘积 ，则 整除 或 整除 ），这个引理本身已经是一个值得单独欣赏的定理，我们在本篇的例题部分给出它的证明。

回到 $1$ 为何不能是素数的问题。如果允许 $1$ 是素数，那么 $12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^{100} \times 2^2 \times 3 = \cdots$，可以无限乘以 ，分解方式就有无穷多种，"唯一性"立刻崩溃。把 排除在素数之外，是保持唯一分解定理成立的逻辑必然，而不是数学家的任意约定。这也解释了为什么 在整数乘法中的角色是"乘法单位元"而非"乘法原子"——它在乘法下不改变任何东西，就像加法中的 一样，是结构中性的存在。

素数的无穷性：欧几里得的永恒证明

认识了素数的定义、判断方法与分解定理之后，一个必然浮现的问题是：素数到底有多少个？在越来越大的数里，我们不断发现新的素数，但这个过程会在某处停止吗？

这个问题在公元前约 $300$ 年就被欧几里得彻底解决了，他的证明极其简洁，被数论学家和普通数学爱好者共同推崇为数学史上最美的证明之一。

定理：素数有无穷多个。

证明采用反证法。假设素数只有有限个，将它们全部列出为 $p_1, p_2, \ldots, p_k$。构造一个新的正整数

$N = p_1 \times p_2 \times \cdots \times p_k + 1.$

现在审问 $N$ 的身份：$N$ 要么是素数，要么是合数，两种情况都将导致矛盾。若 $N$ 是素数，则它是一个不在原列表中的新素数（因为 $N$ 显然大于所有 $p_i$），与"已将所有素数列出"矛盾。若 $N$ 是合数，由算术基本定理， 有某个素因子 。但 不可能是任何 ，因为 除以任意 的余数都是 （由构造方式，，所以 但 ），于是 是一个既非任何 又是素数的数，同样与"已将所有素数列出"矛盾。两种情况都不可能，"素数有限"的假设宣告破产，素数只能是无穷多个。

值得注意的是，欧几里得的构造方法并不是一台"生产新素数的机器"——$N = p_1 \cdots p_k + 1$ 本身不一定是素数，有时它也可能是合数（例如 $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$），但它的素因子 和 都不在原列表 中，矛盾依然成立。这个细节常常被初学者误解，以为欧几里得的证明直接构造了新素数，实际上证明的力量来自"无论 是哪种情形，原列表都无法穷尽所有素数"这个逻辑。

素数的分布：越稀疏，却永不终止

素数有无穷多个，但它们在数轴上的分布是高度不均匀的。在前 $100$ 个正整数中，素数有 $25$ 个，密度约为 $25\%$；在前 $1000$ 个正整数中，素数有 $168$ 个，密度约 $16.8\%$；前 $10000$ 个里有 $1229$ 个，约 ；前 个里有 个，约 。随着范围扩大，素数变得愈发稀疏，但永远不会彻底消失。

数学家用素数计数函数 $\pi(x)$ 表示不超过 $x$ 的素数个数。$19$ 世纪末由阿达马（Hadamard）和瓦莱·普桑（de la Vallée Poussin）独立证明的素数定理给出了精确的渐近描述：

$\pi(x) \sim \frac{x}{\ln x}, \quad x \to \infty$

这意味着在 $x$ 附近，每隔约 $\ln x$ 个数才会出现一个素数。$x = 10^6$ 时 $\ln x \approx 13.8$，$x = 10^{100}$ 时 ——素数会越来越稀疏，但这条稀疏化的趋势是对数级别的，非常缓慢，永远不会让素数"跑光"。更令人着迷的是，哥德巴赫猜想（每个大于 的偶数都是两个素数之和）和黎曼假设（素数分布与黎曼 函数零点之间的精确联系）至今仍是未解之谜，素数的故事远未结束。

例题精讲

例题一：试除法判断素性

题目：判断 $143$ 是否为素数。

例题二：素因数分解

题目：写出 $360$ 的标准素因数分解。

例题三：埃拉托色尼筛法的实施

题目：用筛法找出 $50$ 以内的全部素数。

例题四：任意大于 $1$ 的正整数必有素因子

题目：证明：若 $n > 1$，则 $n$ 必有至少一个素因子。

例题五：素数整除乘积的关键引理

题目：设 $p$ 是素数，若 $p \mid ab$，证明 $p \mid a$ 或 $p \mid b$。

练习

练习一：判断 $221$ 是否为素数。若是合数，写出它的素因数分解。

练习二：用埃拉托色尼筛法找出 $1$ 到 $30$ 之间所有的素数，并验证：这 $10$ 个素数满足每对相邻素数之差（即"素数间隔"）均不超过 $6$。

练习三：证明：若 $p$ 是素数且 $p \mid n^2$，则 $p^2 \mid n^2$（提示：先由例题五的引理推出 $$）。

要点收束

素数是整数乘法世界的"原子"，是无法被进一步分解的最基本单元。算术基本定理保证了每个大于 $1$ 的正整数都有且只有一种素因数分解，这是整个数论大厦的核心基石，也是 $1$ 被排除在素数之外的根本原因。 判断单个数的素性可以用试除法（只需试到 $\sqrt{n}$，且只试素数），寻找一段范围内的所有素数则用埃拉托色尼筛法，两者背后的效率原理都来自"最小因子不超过 $\sqrt{n}$"这条简单却深刻的观察。

欧几里得用一个反证法——构造所有已知素数之积加 $1$，导出必然存在新素数——证明了素数是无穷无尽的，这个证明历经两千三百年依然无懈可击。 素数分布越来越稀疏，素数定理 $\pi(x) \sim x / \ln x$ 给出了定量描述，而哥德巴赫猜想与黎曼假设则提醒我们，素数的故事远未讲完。

其中 $p_1 < p_2 < \cdots < p_k$ 是素数，$a_1, a_2, \ldots, a_k$ 是正整数。

故 $221 = 13 \times 17$，是合数。两个因子 $13$ 和 $17$ 都是素数，所以这就是 $221$ 的素因数分解。

更一般地，若 $p$ 是素数且 $p \mid n^m$，则 $p^m \mid n^m$，其证明只需对 $m$ 次反复应用该引理即可。这个性质在后续证明$\sqrt{2}$是无理数等经典结论时会用到——"如果 $\sqrt{2} = p/q$ 是最简分数，则 $2q^2 = p^2$，由上述性质 $4 \mid p^2$，继而 $2 \mid p$，矛盾"的论证结构，就是这条引理的直接应用。