素数与合数 | 自在学

素数与合数

上一节我们一直在看“整除”。也就是：一个数能不能刚好除尽另一个数。这一节，我们换个角度看整数本身。有些数可以继续拆开，比如：

12 = 3 \times 4

也可以继续拆成：

12 = 2 \times 2 \times 3

但有些数就不太一样。

比如 $7$ ，你想把它写成两个比它小的正整数相乘，怎么试都不行。

这种“拆不开”的数，就是我们今天要讲的素数。

能被拆开的数，就是合数。

素数与合数的直观图示：正整数按照"能否分解为更小正整数的乘积"分为两类，素数用单一圆圈表示（无法拆分），合数用分叉箭头展示拆分为更小因子的过程，1单独标注为"既非素数也非合数"

素数的定义

判断一个数是不是素数，最直接的方法是看它有几个正因数。

比如 $6$ 的正因数是：

1,2,3,6

它除了 $1$ 和自己以外，还有 $2$ 和 $3$ ，所以 $6$ 可以拆开：

6 = 2 \times 3

再看 $15$ ：

15 = 3 \times 5

它也能拆开，所以 $15$ 不是素数。

但 $7$ 的正因数只有：

1,7

除了 $1 \times 7$ 这种写法，它没有别的拆法。

所以 $7$ 是素数。

素数（质数）的定义：如果一个正整数 $p$ 满足 $p>1$ ，并且它的正因数只有 $1$ 和 $p$ 本身，那么 $p$ 就是素数。

大于 $1$ 的正整数里，不是素数的数叫合数。

也就是说，合数至少还有一个“额外因数”。

这里一定要单独说一下 $1$ 。

$1$ 不是素数，也不是合数。

为什么？

因为素数要有两个正因数： $1$ 和它自己。

但 $1$ 只有一个正因数，就是 $1$ 本身。

它也不是合数，因为它没有办法拆成两个大于 $1$ 的正整数相乘。

所以 $1$ 比较特殊，我们把它单独放在一边。

最小的素数是 $2$ 。

接下来是：

3,5,7,11,13,17,19,23,29,31,\ldots

你会发现，除了 $2$ 以外，其他素数都是奇数。

原因很简单：任何大于 $2$ 的偶数，都能被 $2$ 整除，所以一定不是素数。

因此， $2$ 是唯一的偶素数。

判断素数的方法

试除法：一个一个试

判断一个数是不是素数，最朴素的方法就是试除。

比如要判断 $n$ 是不是素数，就看有没有一个比 $1$ 大、比 $n$ 小的数能整除它。

如果找到了，它就是合数。

如果找不到，它就是素数。

不过，我们不需要一直试到 $n-1$ 。

只需要试到：

\sqrt{n}

为什么？

如果 $n$ 能拆成：

n = a \times b

并且 $a \leq b$ ，那么较小的那个因数 $a$ 一定不会超过 $\sqrt{n}$ 。

所以，只要在 $2$ 到 $\sqrt{n}$ 之间找不到因数，就可以确定 $n$ 是素数。

比如判断 $97$ 。

因为：

\sqrt{97} \approx 9.8

所以只需要试 $2,3,5,7$ 。

$97$ 不能被 $2$ 、 $3$ 、 $5$ 、 $7$ 整除。

因此 $97$ 是素数。

实际做题时，我们通常只试素数。

不用试 $4,6,8,9$ 这类合数，因为如果一个数能被它们整除，通常早就会被更小的素因数发现。

试除法很适合手算小数。

如果是特别大的数，计算机还会用更快的素数检测方法。不过在这里，掌握试除法就够用了。

埃拉托色尼筛法：一次找出很多素数

如果我们不是判断一个数，而是想找出 $1$ 到 $N$ 之间所有素数，就可以用筛法。

它的想法很像筛米。

把合数筛掉，剩下的就是素数。

做法是这样的：

先从 $2$ 开始。

$2$ 是素数，把 $2$ 留下，然后划掉所有 $2$ 的倍数：

4,6,8,10,\ldots

再看下一个没被划掉的数，是 $3$ 。

$3$ 是素数，把 $3$ 留下，然后划掉所有 $3$ 的倍数：

6,9,12,15,\ldots

继续这样做。

每次遇到一个还没被划掉的数，就说明它是素数；然后把它的倍数划掉。

以找 $30$ 以内的素数为例。

先保留 $2$ ，划掉 $2$ 的倍数。

再保留 $3$ ，划掉 $3$ 的倍数。

再保留 $5$ ，划掉 $5$ 的倍数。

因为：

\sqrt{30} \approx 5.48

筛到 $5$ 就差不多了。

最后留下：

2,3,5,7,11,13,17,19,23,29

这就是 $30$ 以内的全部素数。

筛法的好处是：范围很大时，它比一个一个判断快得多。

算术基本定理

素数为什么重要？

因为所有大于 $1$ 的正整数，都可以拆成素数相乘。

而且拆法本质上只有一种。

算术基本定理（唯一分解定理）：每一个大于 $1$ 的正整数，都可以唯一地写成若干素数的乘积。

如果把相同的素数合并成指数形式，可以写成：

n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}

比如：

12 = 2^2 \times 3

60 = 2^2 \times 3 \times 5

360 = 2^3 \times 3^2 \times 5

这些分解就像整数的“乘法身份证”。

顺序可以换，比如 $2 \times 3$ 和 $3 \times 2$ 没区别。

但里面有哪些素数、每个素数出现几次，是确定的。

这也是为什么 $1$ 不能算素数。

如果把 $1$ 也算作素数，那么：

12 = 2^2 \times 3

也可以写成：

12 = 1 \times 2^2 \times 3

还可以写成：

12 = 1^{100} \times 2^2 \times 3

这样一来，分解就不唯一了。

所以 $1$ 必须单独放着，不归入素数。

素数有无穷多个

学到这里，一个很自然的问题会出现：

素数会不会有一天被数完？

答案是：不会。

素数有无穷多个。

这个结论很早以前就由欧几里得证明了，而且证明非常漂亮。

定理：素数有无穷多个。

我们用反证法来想。

假设素数只有有限多个，并且已经全部列出来了：

p_1,p_2,\ldots,p_k

现在把它们全部乘起来，再加 $1$ ：

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

这个新数 $N$ 很关键。

因为它除以列表里的任何一个素数，都会余 $1$ 。

也就是说，列表里的素数没有一个能整除 $N$ 。

那 $N$ 会是什么？如果 $N$ 本身是素数，那它就是一个没在列表里的新素数。

这和“列表已经包含全部素数”矛盾。如果 $N$ 是合数，那它一定有素因数。但这个素因数也不可能在原来的列表里，因为原列表里的素数都不能整除 $N$ 。

这同样说明：还有新的素数没有被列出来。所以，“素数只有有限多个”这个假设不成立。素数必定有无穷多个。

注意，这个证明不是说 $N$ 一定是素数。有时候 $N$ 也可能是合数。

但没关系。

只要 $N$ 有素因数，这些素因数就一定不在原来的列表里。这就是证明最巧妙的地方。

素数的分布

素数有无穷多个，但它们不是平均出现的。

越往后，素数一般越稀疏。

比如：

$100$ 以内有 $25$ 个素数
$1000$ 以内有 $168$ 个素数
$10000$ 以内有 $1229$ 个素数

你会看到，范围越大，素数所占的比例越小。

不过，它们不会消失。

数学家用 $\pi(x)$ 表示“不超过 $x$ 的素数个数”。

素数定理告诉我们：

\pi(x) \sim \frac{x}{\ln x}

这句话不用现在完全吃透。

你可以先把它理解成：在很大的数附近，素数出现得越来越稀疏，但稀疏得很有规律。

素数的分布里还有很多著名难题，比如哥德巴赫猜想和黎曼假设。

所以，素数虽然定义很简单，但背后藏着非常深的数学。

例题精讲

例题一：试除法判断素性

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

先确定要试到哪里。

因为：

\sqrt{143} \approx 11.96

所以只需要试不超过 $11$ 的素数：

例题二：素因数分解

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

从最小的素数 $2$ 开始除。

360 \div 2 = 180

180 \div 2 = 90

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

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

先看筛到哪里。

因为：

\sqrt{50} \approx 7.07

所以筛到 $7$ 就够了。

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

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

看 $n$ 的所有大于 $1$ 的正因数。

这个集合一定不是空的，因为 $n$ 自己就在里面。

取其中最小的一个，记作 $p$ 。

我们说明一定是素数。

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

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

这条性质的意思是：素数如果能整除一个乘积，就一定能整除其中至少一个因子。

我们分情况想。

如果 $p \mid a$ ，结论已经成立。

下面只需要考虑 $p \nmid a$ 的情况。

因为 $p$ 是素数，而又不整除，所以和没有大于的公因数。

练习

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

先算上界：

\sqrt{221} \approx 14.87

所以只需要试：

2,3,5,7,11,13

练习二：用埃拉托色尼筛法找出 $1$ 到 $30$ 之间所有的素数，并验证相邻素数之差均不超过 $6$ 。

$30$ 以内的素数是：

2,3,5,7,11,13,17,19,23,29

相邻差值分别是：

1,2,2,4,2,4,2,4,6

练习三：证明：若 $p$ 是素数且 $p \mid n^2$ ，则 $p^2 \mid n^2$ 。

因为：

n^2 = n \times n

又因为 $p \mid n^2$ ，由例题五的性质可知：

p \mid n

要点收束

这一节我们认识了素数和合数。

素数就是只能被 $1$ 和自己整除的大于 $1$ 的正整数。

合数则可以继续拆成更小的因数。

$1$ 既不是素数，也不是合数，因为它只有一个正因数。

判断素数时，可以用试除法，只需要试到 $\sqrt{n}$ 。

如果要找一段范围内的所有素数，可以用埃拉托色尼筛法。

算术基本定理告诉我们：每个大于 $1$ 的正整数，都能唯一分解成素数的乘积。

欧几里得证明了素数有无穷多个。

虽然素数越往后越稀疏，但它们永远不会消失。这也是素数最迷人的地方：定义很简单，故事却很长。