最后更新: 2023-11-09 18:30 ● 参与者查看: 204 次纠错分享参与项目词条搜索

素数及其判别法

**素数及其判别法**

考察正整数的正因数, 我们发现, 有的正整数仅有一个正因数 (如 1), 有的正整数仅有两个正因数（如 $3,13,31$ ), 而有的正整数至少有三个正因数（如 $12,14,81$ ).
我们把仅有两个正因数的正整数叫做素数, 不是素数又不是 1 的正整数叫做合数.
由定义知, $3,13,31$ 是素数, $12,14,81$ 是合数, 1 既不是素数, 也不是合数.
显然, 2 是惟一的偶素数, 也是最小的素数. 每个合数总可以表示成两个大于 1 的正整数的乘积, 而素数则不能.
观察
找出下列每个正整数的正因数:

$$
6,7,9,21,65,77,121 .
$$

观察每个正整数除 1 外的最小的一个正因数, 从中你能发现什么规律?

我们发现, 每个正整数 $n$ 除 1 外的最小正因数 $p$ 是一个素数. 事实上, 假设 $p$ 不是素数, 因为 $p>1$, 所以 $p$ 为合数, 那么 $p$ 必然有 $1, p$ 以外的正因数 $q$, 使得 $q \mid p$. 因为$p \mid n$, 所以 $q \mid n$, 于是 $q$ 是 $n$ 的除 $1, p$ 以外且小于 $p$ 的正因数, 这与已知矛盾, 故最小正因数 $p$ 是一个素数. 一般地, 任何大于 1 的整数, 总存在一个素数因数. 通常, 把一个正整数的素数因数叫做它的素因数.

对大于 1 的整数 $n$, 如果 $n$ 不是素数, 我们可以将 $n$ 分解为一个素数和某个大于 1 的整数 $a$ 的乘积, 如果 $a$ 是一个素数, 则过程停止. 否则, 又可将 $a$ 分解为一个素数和某个大于 1 的整数 $b$ 的乘积. 对 $b$ 又分两种情形: 若 $b$ 为素数, 则过程停止; 若 $b$ 不是素数, 则将 $b$ 继续分解为一个素数和某个大于 1 的整数 $c$ 的乘积. 如此进行下去, 直到过程停止, 最后总可将 $n$ 分解为一些素数的乘积. 例如, $12=2 \times 2 \times 3,78=2 \times 3 \times 13$.

既然任何大于 1 的整数 $n$ 总可分解为一些素数的乘积, 那么素数有多少个? 有限还是无限? 为什么?

我们不妨假设素数有有限个, 即 $m_1, m_2, m_3, \cdots, m_k$, 记这 $k$ 个素数的乘积为 $N$, 即

$$
N=m_1 m_2 m_3 \cdots m_k \text {. }
$$

由此可知, 任意一个素数 $m_i(i=1,2, \cdots k)$ 都整除 $N$, 但不能整除 $N+1$. 又由于 $N+1$ 为大于 1 的正整数, 所以它一定能被某个素数整除, 这就产生了矛盾. 因此, 假设素数有有限个是错误的, 素数有无穷多个

对给定的大于 1 的正整数, 如何判断它是不是素数呢? 例如, 要判断 61 是不是素数, 是否需要用 $2 \sim 60$ 之间的数- - 试除 61 呢?

没有必要. 因为 2 不是 61 的因数, 那么 2 的倍数也不是 61 的因数. 同样地, 若 3 不是 61 的因数, 那么 3 的倍数也不是 61 的因数. 这就是说只需用 $2 \sim 60$ 之间的素数试除 61 即可.

另一方面, 如果 61 是合数, 那么它一定可以表示成两个大于 1 的正因数的乘积, 其中较小的一个正因数一定不超过 $\sqrt{61}$, 并且它的素因数也是 61 的素因数. 这就是说, 如果 61 是合数, 那么它一定存在不超过 $\sqrt{61}$ 的素因数.
因此只需用 $2 \sim 60$ 之间不超过 $\sqrt{61}$ 的素数试除 61 即可.
不超过 $\sqrt{61}$ 的素数为 $2,3,5,7$, 由于它们都不整除 61 , 所以 61 是素数.

一般地, 我们有下面的判别法:
如果大于 1 的整数 $a$ 不能被所有不超过 $\sqrt{a}$ 的素数整除, 那么 $a$-定是素数.
这个判别法实际上给出了一种寻找素数的有效方法.

例 3 找出 $1 \sim 100$ 中的全部素数.
解：只需把 1 与 $1 \sim 100$ 之间的合数去掉即可. 而对于 $1 \sim 100$ 之间的每个合数 $a$, 它一定能被某个不超过 $\sqrt{a}$ 的素数整除, 从而能被不超过 $\sqrt{100}=10$ 的素数整除. 我们知道,不超过 10 的素数为 $2,3,5,7$. 在 $1 \sim 100$ 中首先去掉 1 , 然后分别去掉 $2,3,5,7$ 除自身以外的倍数, 最后剩下的数就是不超过 100 的全部素数. 具体做法如下表:
![图片](/uploads/2023-11/image_202311095374b7b.png)
因此不超过 100 的素数为 $2,3,5,7,11,13,17,19,23,29,31,37,41,43$, $47,53,59,61,67,71,73,79,83,89,97$, 共 25 个. 这种寻找素数的方法叫做埃拉托斯特尼 (Eratosthenes) 篮法.

上一篇：带余除法

下一篇：最大公因数与最小公倍数

本文对您是否有用？有用 (0) 无用 (0)