拆开 60 这个数字，我发现了密码学最原始的起点 - 每日分享

你有没有试着把 60 拆成“不能再拆”的样子？不是 6 × 10，因为 6 和 10 还能继续拆。真正拆到底，是 2 × 2 × 3 × 5。这四个数就像乐高积木里的最小颗粒，所有其他数字都是用它们拼出来的——这就是质因数分解。

你可能会说：这有什么稀罕的？小学就学过。但请等一下，正因为“拆到底”这件事在数学上这么简单，却又在计算上这么难，才支撑起了你今天上网用的 HTTPS 加密。RSA 加密算法赌的就是：给你一个几百位的合数，你想把它拆回质因数，用全世界的计算机一起算，也要算到宇宙热寂。质因数分解，就是密码学赖以生存的“一夫当关”。

所以，别小看这个“拆积木”的动作。

什么是“最小积木块”？

先理清三个概念：

质数：只能被 1 和它自己整除的数，比如 2、3、5、7。它们是积木里的小方块，不能再拆。
合数：除了 1 和它自己，还能被其他数整除，比如 4、6、8、9、12。合数一定能拆成若干质数相乘。
质因数：合数拆开后得到的那些质数。12 = 2 × 2 × 3，所以 12 的质因数是 2 和 3，其中 2 出现了两次。

“出现两次”这个细节很重要。它不是“两个不同的质因数”，而是“同一个质因数用了两次”。很多初学者在数质因数个数的时候会栽在这里，后面我们会看到，这个细节在一道经典题目里恰好是解题的关键。

Python 怎么拆？试除法

最朴素的想法就是“试”：从最小的质数 2 开始，看看能不能整除。能整除，就记下来，把数字缩小；不能整除，试下一个数。一直试到数字变成 1。

但这里有个优化：循环只需要到平方根。为什么？因为如果一个合数 n 有一个大于 √n 的因子，那它必然也有一个小于 √n 的因子。比如 12，√12 ≈ 3.46，我们试到 3 就够了。3 除不尽 12 之后，剩下的 n 是 1，结束。实际上，12 的两个质因数 2 和 3 都小于等于 √12。如果 n 是质数，比如 97，试到 √97 ≈ 9.8 都除不尽，最后 n 还是 97，那 97 本身就是质因数。

代码可以这样写：

def prime_factorization(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

核心就三件事：

从小往大试除，能整除就记录并缩小 n。
循环只到平方根，省时间。
循环结束后，如果 n 还大于 1，那它一定是一个质数，直接收尾。

这里有个许多新手容易漏掉的地方：忘记处理最后剩下的 n。比如输入 97，循环里啥也没干，循环结束后 n 还是 97。如果你不加 if n > 1: factors.append(n)，结果就是空列表——明明 97 本身是个质数，却一个因子都拆不出来。写代码时，一定要记得“最后剩下的那一粒面粉本身就是质因数”。

用筛子筛面粉

把整个过程想象成筛面粉：你先用 2 号筛子筛，把所有能筛出的“2”都筛出来；再换 3 号筛子，筛出“3”；再换 4 号筛子——注意，4 号筛子实际上已经筛不出任何东西了，因为如果 n 能被 4 整除，它一定先能被 2 整除，而 2 已经在前面被筛干净了。所以代码里 d += 1 不管 d 是不是质数都无所谓，合数筛子注定是空的。这就像你筛完 2 之后，4、6、8 这些筛子自然什么也筛不出来。等到筛子孔比剩下的面粉粒还大（即 d*d > n），停止。剩下那一粒面粉，本身就是质地最纯的质数面粉——直接收进袋子里。

这道题，正好考了“指数”的敏感度

质因数分解不只是个数学游戏，它在很多编程题里都是隐藏的关键。比如有一道经典题：求 N 的阶乘最右边的非零位。

N 可以大到 5000 万，直接算阶乘？不可能，数字位数比宇宙原子总数还多。但我们可以用质因数分解的思路：阶乘的最右边非零位，本质上是把所有因子中的“10”先剥离掉。10 = 2 × 5，所以只要统计 1 到 N 里有多少对 2 和 5，把它们约掉，剩下的数字相乘，再取个位就行。

这里就用到质因数分解的思想，但不需要真的分解 N！，只需要分解 1 到 N 里的每一个数，统计 2 和 5 的个数。比如 N=12 时，1 到 12 里因子 2 的个数远比因子 5 的个数多，5 只有 5 和 10 各贡献一个，一共两个。所以把多余的 2 去掉后，剩下的所有因子乘积的个位就是答案。答案是 6。

这道题的关键点在于：你不需要把整个阶乘算出来，只需要看质因数里 2 和 5 的数量关系。这正体现了质因数分解的威力——把大问题拆成小积木，再数积木块的数量。

类似地，还有一道“求完数”的题目：输入 N，输出小于 N 的所有完数。完数的定义是“一个数等于它所有真因子之和”，比如 6 = 1 + 2 + 3。怎么高效地找因子？如果你对每个数都从 1 试到它自己，复杂度是 O(N²)，当 N 接近 10000 时还能忍，但如果 N 更大就麻烦了。利用质因数分解，可以快速生成所有因子，然后求和。比如 28 = 2² × 7，它的因子是 1、2、4、7、14、28，真因子之和 1+2+4+7+14 = 28，所以 28 是完数。质因数分解在这里不是直接解题，而是提供了一种高效枚举因子的思路。

别把“质因数列表”和“质数判断”混为一谈

有人会问：能不能用质因数分解来判断一个数是不是质数？可以，但要注意一个陷阱：只有一个质因数不等于质数。比如 4 = 2 × 2，质因数列表是 [2]，只有一个质因数，但 4 是合数。正确的是：质因数分解结果中只有一个质因数，并且这个质因数等于原数，原数才是质数。也就是说，对于质数 13，分解结果是 [13]，13 == 13，成立。对于 4，分解结果是 [2]，2 ≠ 4，所以是合数。

这个陷阱在题目里经常出现。很多人只看到“列表长度 = 1”就下结论，忽略了质因数可以重复出现。区分“质因数个数”和“质因数的指数”是关键。

从试除法到 RSA：我们才刚刚推开门

如果你以为质因数分解就是“循环加取余”，那你就错过了它最迷人之处。试除法只在数字小的时候有效。当 n 是 10 位数时，试除法还能勉强工作；当 n 是 300 位数时，试除法需要 10^150 次计算，宇宙的年龄都不够用。而 RSA 加密正是建立在“大数分解极其困难”这一假设上。换句话说，我们今天写的这个简单函数，在数字变大后，会变成一个不可能完成的任务。

但也正因为如此，质因数分解才显得更重要。理解它的原理，是理解现代密码学的第一步。你可以试着改进代码：比如跳过所有偶数、只试质数、用 Pollard Rho 算法……这些方向都能让你对算法复杂度有更深刻的认识。

最后，留一个思考题给你：质因数分解的结果用指数形式表示（比如 360 = 2³ × 3² × 5）该如何输出？试着修改你的代码，让它打印出更接近数学表达的格式。这一步能帮你更好地理解“指数”和“因子”的关系，也是通往数论更深处的钥匙。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）