最后更新: 2026-05-23 07:07 查看: 395 次纠错评论(0) 课件开VIP

素数及其判别法

## 取整函数
在进行下面讲解前，引入一个函数：取整函数。
我们用符号 $[x]$ 表示不超过实数 $x$ 的最大整数。

比如： $[2.5]=2$ , $[-2.5]=-3$

> 特别要注意负数，$[-2.5]=-3$ 而不是 $[-2.5]=-2$

## 素数及其判别法

考察正整数的正因数, 我们发现, 有的正整数仅有一个正因数 (如 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 外的最小的一个正因数, 从中你能发现什么规律?

``` 
6=2 *3
7=1 *7
9=3*3
21=3*7
65=5*13
77=7*11
121=11*11

```

我们发现, 每个正整数分解到最后都是一系列素数的乘积，即最小正因数 $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： 任何整数都可以分解为多个素数的乘积。**

对大于 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$.

> **结论2：素数有无限个**

`例`证明素数有无限个。
证明：反证法证明：素数有无穷多个
假设**素数只有有限个**，设全部素数为：
$$p_1,p_2,p_3,\dots,p_n$$

构造新整数：
$$N = p_1p_2p_3\cdots p_n + 1$$

1. $N>1$，则$N$要么是素数，要么能被某个素数整除。
2. 用任意已知素数$p_i$除$N$：
$$N\div p_i = k\cdots\cdots1$$
余数恒为$1$，**所有已知素数都不能整除$N$**。

- 若$N$是素数：它不在原先有限素数列表中，矛盾；
- 若$N$是合数：它必有素因子，该素因子也不在原列表中，矛盾。

因此**素数有限**的假设不成立。
**结论：素数有无穷多个。**

上面这个证法是欧几里得最先给出的证明，因此也叫做欧几里得素数无限法。

![图片](/uploads/2026-05/7d7c86.jpg){width=100px}
 欧几里得

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

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

另一方面, 如果 61 是合数, 那么它一定可以表示成两个大于 1 的正因数$p,q$的乘积, 其中较小的一个正因数一定不超过 $\sqrt{61}$, 并且它的素因数也是 61 的素因数. 这就是说, 如果 61 是合数, 那么它一定存在不超过 $\sqrt{61}$ 的素因数.

因此只需用 $2 \sim 60$ 之间不超过 $\sqrt{61}$ 的素数试除 61 即可.

> 通过上面介绍可以得到，要判断一个数$n$是否是素数，当进行列举时，只要从$2,3,5... \sqrt{n}$ 进行实验即可。

不超过 $\sqrt{61}$ 的素数为 $2,3,5,7$, 由于它们都不整除 61 , 所以 61 是素数.

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

根据定义，判断数 $n$是否为素数，只需看它能否被 $2$到$\sqrt{n}$之间的整数整除。下面给出python代码实现

``` 
import math

def is_prime_better(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 检查从 3 到 sqrt(n) 的奇数
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
```

`例`找出 $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/2025-06/51326c.jpg)
 
因此不超过 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) 筛法**.

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：带余除法与二进制

下一篇：最大公因数GCD

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