质数基础

定义

质数（prime），指大于 $1$ 的自然数里，不能拆解为比它严格更小两个的自然数乘积的数。¹

互质（co-prime），两个整数 $a$，$b$ 没有除了 $1$ 以外的作为正整数的共同除数（divisor），则说 $a$ 质于 $b$ ，或者 $a,b$ 互质²。³

性质

欧几里得引理

欧几里得引理⁴，

原始版本：如果质数 $p$ 能够除 $a\cdot b$ ⁵，并且 $p$ 不能除 $a$ ，则 $p$ 能够除 $b$ 。

现代版本：如果一个整数 $n$ 能够除 $a\cdot b$ ，并且 $n$ 与 $a$ 互质，则 $n$ 能够除 $b$ 。

证明

现代版是把原始欧式引理推广到一般整数上，我们直接对此进行证明。

不妨假设 $n$ 是非负数：

证初始条件

对于初始情况，比如 $ab = 0$ ，此时 $a=0$ 或 $b=0$ 。

假设 $a=0$ ，因为 $n\perp a$ ，那么显然有 $n = 1$ ，而 $1$ 可以除任何数，当然能够除 $b$ ，结论成立；

假设 $b=0$，$b$ 能够被任何数整除，当然能被 $n$ 整除，条件成立。

证递推关系

假设结论对于所有积在 $[0, ab)$ 的情况结论都成立：

因为 $n \vert a\cdot b$ ，不妨令

如果 $n=a$ ，因为 $n\perp a$ ，那么显然有 $\vert n \vert = 1$ ，那么 $n$ 一定可以除 $b$ ；

如果 $n\lt a$ ，两边减去 $n\cdot b$ ，得到 $nq - nb = ab - nb$ ，也就是 $n(q-b) = (a-n)b$ 。又因为 $n\perp a$ ，所以有 $n\perp a-n$ ⁶ ，而 $0 \leqslant (a-n)b \lt ab$ ，按照假设，有 $n \vert b$ ；

否则 $n \gt a$，两边减去 $a\cdot q$ ，得到 $nq-aq = ab-aq$ ，也即

类似地， 因为 $n-a\perp a$ ，而 $0 \leqslant a(b-q) \lt ab$ ，所以有 $(n-a)\ \vert\ (b-q) $ 。不妨令 $b-q = r(n-a)$ ，代回式 $\texttt{(2)}$ 得到 $(n-a)q=(n-a)ar$ ，于是有 $q=ar$ ，代回式 $\texttt{(1)}$ 有 $nar=ab$，$b=nr$ ，也就是 $n \vert b$ 。

于是我们证明了递推关系的成立。

证毕。

算式基本定理

算式基本定理⁷，每一个大于 $1$ 的正整数都可以，而且唯一地分解为一组质数的乘积。

证明

存在性证明

这很容易理解，假如一个大于 $1$ 的正整数的因式分解不是质数就是合数，因式分解后，如果存在合数，那么合数本身也一定可以继续分解，直到只剩下质数为止。

唯一性证明

反证法，假设 $s$ 是最小的、至少有两个质数分解组合的正整数：$s = \prod p_m = \prod q_n$ 。

既然 $p_1 \perp q_k$ ，根据上文欧式引理，有 $p_1 \vert\prod_{1}^{n-1} q$；同理，$p_1 \perp p_{k=n-1}$ ，可得 $p_1 \vert \prod_{1}^{n-2} q$ ；直到 $p_1 \vert q_1$ 。

又因为 $p_1 \perp q_1$ ，所以只能是 $p_1 = q_1$ ，这样就得到了比 $s$ 更小的能分解为至少两个质数组合的正整数 $\prod_{2}^{m} p = \prod_{2}^{n} q$ ，与前提假设相悖，于是反证成立。

唯一性证明（独立）

这里通过不依赖欧几里得引理来独立证明。

仍然通过反证法，假设 $s$ 是最小的、至少有两个质数分解组合的正整数 $s = \prod p_m = \prod q_n$ 。

如果两个组合里存在一对儿相等的质数 $p_i = q_j$ ，则两边约掉相等的数后会出现一个比 $s$ 更小的多质数分解的整数，与前提相悖。

因此不妨可以假设 $p_1 \lt q_1$ ，令 $P=\prod_{2}^{m} p$ ，$Q=\prod_{2}^{n} q$ ，则有 $s=p_1P=q_1Q$ 。

又有 $p_1 \lt q_1$ ，所以 $P \gt Q$ ，不妨令 $s’$ 等于 $s$ 减去 $p_1Q$ ，得到 $s’ = p_1(P-Q) = Q(q_1-p_1)$ 。因为 $ s’ \lt s$ ，所以 $s’$ 只有唯一的质因数分解，那么 $p_1$ 要么在 $q_1 - p_1$ 的部分，要么在 $Q$ 的部分。

如果 $p_1$ 在 $q_1-p_1$ 的部分，则有 $p_1 \vert q_1$ ，与 $p_1$ 、$q_1$ 都是质数相悖；

如果 $p_1$ 在 $Q$ 的部分，由于前面的结论，$p_1 \not\in \lbrace q \rbrace$ ，因此就有两对儿质因数分解，这样就发现了比 $s$ 更小的多组质因数分解的正整数 $Q$ ，与假设相悖。

反证证毕。

质数分布

质数定理

质数定理⁸，首先定义一个用于质数计数的函数 $\pi(N)$ ，表示 $\leqslant N$ 范围内的质数个数，那么有：

据此，也可以推出第 $n$ 个质数 $p_n$ 的渐进表示：

推理过程：

首先这实质是在求 $\pi(x)$ 的反函数（的渐进表示），已知 $y\sim\large\frac{x}{\log x}$ ，两边取 $\log$ 得到 $ \log y \sim \log x - \log\log x \sim \log x$ ⁹，带回 $\pi(x)$ 原式得到 $x \sim y\log y$ ，也即 $p_n \sim \large\frac{n}{\log n}$ ，证毕。

伯特兰-切比雪夫定理

伯特兰-切比雪夫定理¹⁰，对于 $n > 3$ ，至少存在一个质数 $p$ ，满足 $n \lt p \lt 2n-2$ 。

更宽松、但更适用的形式是对于 $n\geqslant 2$：

证明很简单，首先对于 $n\gt 3$ 的情况，显然由于更宽松的形式，上式是成立的；而对于 $n=2$ 和 $n=3$ 的特殊情况，分别有 $2 \lt 3\lt 4$ 和 $3 \lt 5\lt 6$ ，也使得上式成立。

通过反证法还可以得出对于 $n\geqslant 1$ ，也就是所有质数：

质性测试

这里将介绍简单的测试方法¹¹ – 试除法（trial division），其中使用的技巧将在后面查找范围内所有质数的方法里得到进一步的拓展。

被测试的整数记为 $n$ ，试除法，顾名思义就是检查所有 $2\dots n-1$ 的值能否除 $n$ ，也就是根据原始定义进行测试。这里主要介绍常见的优化技巧：

首先，因数测试的上限不需要到 $n-1$ ，而只需要到 $\lfloor \sqrt{n} \rfloor$ ¹² ，因为因数如果存在，一定是一大一小或者相等大小，只需要检查所有较小或者相等的数就行。

其次，可以先检测大多数情况下最常见的质因数：$2, 3$ 来快速失败。

更进一步地，可以排除所有与 $2,3$ 不互质的数，实质上我们是在尝试寻找 $n$ 的质因数，可以用 $3\sharp\cdot k+i = 6k+i$ ¹³的形式表示后面的数字，其中 $k \in N^+, 0\leqslant i \lt 3\sharp$ 。

之所以选择 $3\sharp$ 作为周期长度，是因为它是这些质因子的最小公倍数，在此基础上排除那些与 $2$ 或 $3$ 不互质的 $i$ ，比如 $i=0, 2, 4$ ，也就是只需要检查 $6k+1, 6k+5$ 。假如从数字 $5$ ¹⁴开始检查是否能除 $n$ ，那么为了方便起见，周期内的这两个位置 $x$ 可以表示为 $x \mod{6} \equiv \pm1$ 。

有了这样三个主要地优化，现在就可以写下试除法的代码：

#[macro_export]
macro_rules! is_prime {
    ($n:expr; $ty:ty) => {
        {
            let n = $n;

            'ret: loop {
                if n <= 1 {
                    break false;
                }
                
                if n == 2 || n == 3 {
                    break true;
                }

                if n % 2 == 0 || n % 3 == 0 {
                    break false;
                }

                for i in (5..=<$ty>::isqrt(n)).step_by(6) {
                    if n % i == 0 || n % (i+2) == 0 {
                        break 'ret false
                    }
                }

                break true
            }
        }
    };
}

这里使用宏只是因为 Rust 缺乏统一描述常见基本数字类型的 Trait ，而使用 loop 是为了在宏里模拟函数体行为。

查找质数

具体来说，是这样一个问题：给定一个正整数 $N$ ，查找所有质数 $p\leqslant N$ 。¹⁵

方法论是通过“筛子” （Sieves）来排除合数，直到只剩质数，这种缩减问题规模的办法，也是数学上对此类问题的通解。

详见专篇：质数筛子

注解