素数、素数无穷与算术基本定理

素数看起来只是「除了 $1$ 和自身没有别的正因数」，真正要回答的却有三问：这样的数有多少个、每个大于 $1$ 的整数能不能拆成素数、拆法是不是唯一。下面按这条线索把定义、证明思路、手算和代码放在一起。

素数在说什么

大于 $1$ 的正整数 $p$，若正因数只有 $1$ 和 $p$，就叫素数（质数）。大于 $1$ 且不是素数的正整数叫合数。于是每个大于 $1$ 的正整数恰好落在两类里：要么素数，要么合数。

$1$ 两边都不进。它只有一个正因数，既不是素数也不是合数，在乘法里扮演单位元：$1\cdot n=n$。把 $1$ 算作素数，后面的唯一分解立刻崩掉，因为可以随便添上若干个 $1$。

整除是后面所有话的底层。整数 $a$ 整除 $b$，记作 $a\mid b$，意思是存在整数 $k$ 使 $b=ak$。素数定义看的是正因数，不是「看起来能不能整除」的口头规则。两个大于 $1$ 的整数若没有公共素因子，就叫互素，此时 $$。互素不等于「两个都是素数」： 和 互素，但都是合数； 和 有公共素因子 ，不互素。

最小的几个素数是

其中 $2$ 是唯一的偶素数：任何更大的偶数都能被 $2$ 整除，因此一定是合数。

合数一定有一个不太大的素因子。若 $n$ 是合数，则可写成 $n=ab$，其中 $1<a\le b<n$。此时 $a\le\sqrt{n}$，而 至少有一个素因子 ，于是 且 。这就是试除法只要检查到 的原因。

素数有无穷多个

欧几里得的证明不构造「下一个素数」，只说明：假定只有有限个，就会推出矛盾。

设素数只有有限个，记作 $p_1,p_2,\dots,p_k$，其中 $p_1=2$。考虑

则 $N>1$，所以 $N$ 至少有一个素因子 $q$。但 $q$ 不能是任何一个 $p_i$：否则 $p_i$ 同时整除乘积和 ，也就整除它们的差 ，这不可能。于是出现了名单之外的素数，与「只有这 个」矛盾。

所以素数无穷。

这个论证给出的 $N$ 本身不必是素数。例如前四个素数 $2,3,5,7$ 给出 $N=210+1=211$，碰巧是素数；前六个给出 $N=30031=59\cdot 509$，是合数，但 和 都不在前六个里。证明需要的只是「 带出一个新素因子」，不是「 自己是新素数」。

也可以不先假定「这就是全部素数」。任意取出有限个素数 $p_1,\dots,p_k$，同样令 $N$ 为它们的积加一，则 $N$ 的素因子都不在这张表里。于是任意有限表都补不全，素数集合不能有限。两种说法是同一论证。

手算时常见误读是：把 $N$ 当成「第 $k+1$ 个素数」。从 $2$ 出发依次把已有素数乘起来再加一：$2$，$2+1=3$，$2\cdot 3+1=7$，，下一步 ，已经不是素数。证明仍然成立，只是新素数是 ，不是 。

无穷并不等于「越来越大还很密」。素数定理说第 $n$ 个素数大约是 $n\ln n$，小于 $x$ 的素数大约有 $x/\ln x$ 个，那是分析数论。初等证明只解决有没有尽头。

算术基本定理

算术基本定理（唯一分解定理）说：每个大于 $1$ 的整数 $n$ 都能写成有限个素数的乘积

并且在不计次序时写法唯一。把相同的素因子收在一起，就是标准形

其中 $p_1<p_2<\cdots<p_k$ 是素数，$a_i\ge$。这时指数也唯一。

例如

没有第二种素因数分解。$1$ 约定成空积，指数全是 $0$，所以定理从大于 $1$ 的整数说起即可。

存在性和唯一性要分开证。存在性用「最小反例」，唯一性要用欧几里得引理。

存在性：总能拆开

若存在大于 $1$ 且不能写成素数乘积的正整数，取其中最小的一个，记作 $n$。$n$ 不能是素数，否则它自己就是一种分解。于是 $n$ 是合数，$n=ab$，且 $1<a,b<n$。由最小性， 和 都能分解成素数乘积，拼起来就是 的分解，矛盾。

所以这样的反例不存在：每个大于 $1$ 的整数都能分解。

也可以用归纳：对 $2$ 显然；假设小于 $n$ 的都已分解，再看 $n$ 是素数还是合数，合数就拆成两个更小的因子。两种写法是同一件事。

例如要分解 $60$。它不是素数，$60=6\cdot 10$。再拆：$6=2\cdot 3$，$10=2\cdot 5$，拼起来 。存在性并不指定先拆哪一对： 或 ，最后都会停在素因子。能收到同一张表，靠的是下一节的唯一性；存在性只保证每条拆法都会在有限步结束。

唯一性：欧几里得引理

先要一条整除性质，常叫欧几里得引理：若素数 $p$ 整除乘积 $ab$，则 $p\mid a$ 或 $p\mid b$。

证明靠裴蜀定理。若 $p\nmid a$，则 $\gcd(p,a)=1$，于是存在整数 $x,y$ 使

两边乘 $b$：$abx + pby = b$。左边两项都能被 $p$ 整除，故 $p\mid b$。

对多个因子同样成立：若 $p\mid a_1 a_2 \cdots a_m$，则 $p$ 整除其中某一个 $$。对因子个数做归纳即可。

现在证分解唯一。设

两边都是素数（允许重复）。则 $p_1$ 整除右边，由引理，$p_1$ 等于某个 $q_j$。两边约掉这个素因子，对更小的整数用归纳，两边的素数表在重排后完全一样。

写成标准形时，若同一素数在两边的指数不同，约掉较小的那边后，该素数仍整除另一边，但不再整除约剩的那些不同素数的乘积，同样矛盾。所以指数也唯一。

引理里「$p$ 是素数」不能改成合数。$6$ 整除 $4\cdot 9=36$，但 $6$ 既不整除 $4$ 也不整除 $9$。唯一分解依赖的是素数的这个不可再分的整除性质。

假如有人写出 $12=2\cdot 2\cdot 3=2\cdot 6$，后一种不合法，因为 $6$ 不是素数。合法写法只能是 $2\cdot 2\cdot 3$ 和它的重排。若真有两种本质不同的素因子表，引理会强迫左边每个素数出现在右边，两边约完后应同时变成 $$，不会剩下另一套素数。

手算例子

例一：写出标准分解

把 $840$ 拆成标准形。先剥偶数：$840=2\cdot 420=2^2\cdot 210=2^3\cdot 105$。。于是

验算：$8\cdot 3\cdot 5\cdot 7=8\cdot 105=840$。

例二：用分解做乘法算术

一旦有了标准形，gcd 和 lcm 就是对每个素数取指数的最小或最大：

其中 $v_p(n)$ 是 $n$ 的分解里 $p$ 的指数，没有则视为 $0$。于是恒有

例如 $a=840=2^3\cdot 3\cdot 5\cdot 7$，$b=360=2^3\cdot 3^2\cdot 5$，则

且 $120\cdot 2520=302400=840\cdot 360$。

例三：为什么 $1$ 不能当素数

若允许 $1$ 出现在分解里，$6=2\cdot 3=1\cdot 2\cdot 3=1\cdot 1\cdot 2\cdot 3$，写法立刻不唯一。定理把「不计次序」说清楚，却绝不能把 放进素因子表。

例四：一个数不是素数，也不等于「看起来像分解」

$91=7\cdot 13$，不是素数。试除时若只检查了 $2,3,5$ 就停，会误判它为素数，因为 $\sqrt{91}\approx 9.5$，还必须检查 。这和「分解存在」不冲突：存在性保证能拆开，并不保证你检查的因子够多。

例五：由标准形数约数

标准形还直接给出正约数个数。若 $n=p_1^{a_1}\cdots p_k^{a_k}$，每个素因子的指数可从 取到 ，故

$360=2^3\cdot 3^2\cdot 5$ 有 $(3+1)(2+1)(1+1)=24$ 个正约数。没有唯一分解，这个计数会因拆法不同而打架。

试除与筛法

判断单个 $n$ 是否为素数，最直接的是试除：检查 $2$ 到 $\lfloor\sqrt{n}\rfloor$ 有没有因子。合数必有不超过根号的素因子，所以这个范围充分。

$2$ 和 $3$ 先特判，之后只检查 $6k\pm 1$ 形式的候选：其余整数必被 $2$ 或 $3$ 整除。循环条件写成 $f*f<=n$，避免先算浮点平方根再取整带来的误差。

要分解单个 $n$，同样试除，并一边收集素因子：

例如 factor(840) 得到 [2, 2, 2, 3, 5, 7]，与前面的标准形一致。最后若剩下 $n>1$，它本身就是一个大于 $\sqrt{\text{原数}}$ 的素因子，至多一个。

要一次列出 $2$ 到 $n$ 的全部素数，埃拉托斯特尼筛法更合适：从 $2$ 开始，每遇到一个还没被划掉的数 $p$，就把 $p,2p,3p,\dots$ 中大于 $p$ 的倍数标成合数。剩下的都是素数。

以 $n=20$ 为例。从 $2$ 划掉 $4,6,8,10,12,14,16,18,20$；下一个未划掉的是 $3$，从 起划掉 ；下一个是 ，而 ，停止。剩下 。

筛法的起点写成 $p^2$ 即可：更小的倍数 $2p,3p,\dots,(p-1)p$ 已经在筛更小素数时被划掉。时间大约是 $O(n\log\log n)$，空间 。 到 量级时，比逐个试除每个数要快得多。

线性筛（欧拉筛）让每个合数只被最小素因子划掉一次，时间 $O(n)$，适合还要顺便记录最小素因子、批量分解。对「只要素数表」这件事，埃氏筛已经够用。

写代码时容易踩的坑

$1$ 和负数都不是素数。is_prime(1) 必须是 False；题目若给负数，先规定定义域，不要让 -2 因 % 的行为而误判。

试除上界是 $\lfloor\sqrt{n}\rfloor$，不是 $n/2$。写成 i * i <= n 比 i <= int(n**0.5) 稳：大整数的浮点根号可能略小，会漏掉卡在边界上的因子。

筛法的数组长度是 $n+1$，下标就是数值本身。[True] * n 会让最大的下标变成 $n-1$，漏掉 $n$ 自己。

从 $p^2$ 开始划倍数，不要从 $2p$ 开始也能对，只是慢一些；但不要从 $p$ 开始，否则会把素数自己划掉。

factor 在循环结束后要把剩余的 $n$ 收进去。漏掉这一步，$25=5\cdot 5$ 还好（$5$ 会在循环里除尽），但 $91=7\cdot 13$ 会只得到 [7]，把 $13$ 弄丢。

不要用「除了 $2$ 以外的奇数都可能是素数」去代替完整试除。$9,15,21,25,27,35$ 都是奇数合数。个位规则也一样：它只能排除 $2$ 和 $5$ 的倍数，排除不了 $7,11,13$ 的倍数。 个位是 ，仍是合数。小规则只能加速，不能当充要条件。

sieve 里切片赋值的长度必须和划掉的下标个数一致。is_p[start:n+1:p] 的元素个数是 (n-start)//p+1，少写一个会抛错，多写一个会越界。

唯一分解是对整数乘法说的，不能照搬到别的环里。在 $2\mathbb{Z}$ 这类偶数环里，$6=2\cdot 3$，但 $3$ 不是该环的元素；在某些代数整数环里，不可约元分解可以不唯一。初等数论里我们只在 $\mathbb{Z}$ 上用这套语言。

它在算法里站在哪一层

许多计数和构造都先回到标准形。求 $\gcd$ 不必真的分解，辗转相除更快；但一旦需要「$n$ 有哪些素因子」「无平方因子」「欧拉函数 $\varphi(n)$」，分解就是输入。筛法给出小范围内的素数表，试除给出单个中等整数的因子，两者都是在落实「存在性」：定理保证分解在，算法负责把它找出来。

唯一性则保证这些函数定义清楚。$\varphi(n)=n\prod_{p\mid n}(1-1/p)$ 里的乘积不会因为换一种拆法而改变；判断完全平方只要看每个指数是否为偶数，不会出现两种互相打架的结论。

所以不必把素数表看成一张要背的清单。无穷保证材料够用，唯一分解保证写法只有一种。把定义、存在、唯一三件事分开，手算和代码就会对得上。