质因数分解 - CSP-J | C++ & Algorithm 编程研习社

把合数拆成质数——质因数分解全攻略

每个合数都可以写成几个质数相乘的形式，就像搭积木时，一个复杂的模型可以被拆成最基础的小积木块。这些“小积木块”就是质因数。比如数字 12 可以拆成 2 × 2 × 3，其中 2 和 3 都是质数（只能被 1 和自己整除的数）。把合数拆成质因数相乘的过程，就叫 质因数分解。

为什么要学质因数分解？

生活小例子：老师要把 90 块糖平均分给几个小组，每组人数一样多，怎么分最快？如果知道 90 = 2 × 3 × 3 × 5，那就可以分成每组 2 人（45 组）、3 人（30 组）……所有分法都是从质因数组合出来的。
数学大用处：求两个数的 最大公约数（GCD） 或 最小公倍数（LCM） 时，只需要把它们的质因数找出来，然后取公共部分或全部部分相乘。比如 12 和 18 的质因数：12=2×2×3，18=2×3×3，公共质因数是 2 和 3，所以最大公约数=2×3=6。
隐藏的密码：在计算机安全中，RSA 加密算法就是利用“大数很难分解质因数”这个性质来保护我们的密码和银行卡信息的。对你们来说，先学会分解小数字，未来才能理解更酷的技术。

质因数分解的关键步骤

从最小的质数 2 开始试除
把合数除以 2，如果除得尽，就记下 2，并且把商继续除以 2；一直除到除不尽为止。
换下一个数继续试
除不尽 2 了，就试试 3、4、5……你可能会想：“4 不是质数，也要试吗？”——其实不用怕，因为如果 n 能被 4 整除，那它肯定已经被 2 除干净了（因为 4=2×2）。所以我们直接从 2 开始，逐个整数往上试就行，相当于自动跳过了合数。
什么时候停止？
当试除的数 d 的平方大于当前剩下的 n 时，就停。因为如果 n 有一个大于 √n 的因数，那它一定有一个小于 √n 的因数在前面已经被试过了。最后如果剩下的 n 大于 1，它自己就是一个质因数。

举个例子：分解 30

30 ÷ 2 = 15，记下 2。
15 ÷ 2 除不尽，换 3：15 ÷ 3 = 5，记下 3。
5 ÷ 3 除不尽，换 4：5 ÷ 4 除不尽，换 5：5 ÷ 5 = 1，记下 5。
得到 30 = 2 × 3 × 5。

代码实现：把分解过程写成 Python 函数

下面这个函数可以把一个整数分解成质因数列表，并返回列表。每一行都加了中文注释，方便理解。

def prime_factors(n):
    """
    返回整数 n 的质因数列表（从小到大）
    """
    factors = []          # 用来存放质因数的空列表
    d = 2                 # 从最小的质数 2 开始试除

    # 当 d*d <= n 时继续循环，避免检查大于平方根的因数
    while d * d <= n:
        # 如果能被 d 整除，就反复除干净，并记下 d
        while n % d == 0:
            factors.append(d)   # 把 d 加入列表
            n //= d             # n 除以 d，得到新的 n
        d += 1                  # 试下一个整数

    # 循环结束后，如果 n 还大于 1，说明它本身是一个质因数
    if n > 1:
        factors.append(n)

    return factors

# 测试几个数
print(prime_factors(12))   # 输出 [2, 2, 3]
print(prime_factors(100))  # 输出 [2, 2, 5, 5]
print(prime_factors(97))   # 97 是质数，输出 [97]
print(prime_factors(1))    # 1 不是合数，输出 []

逐行解释：

while d * d <= n: 保证了我们最多只检查到 √n，大大减少计算次数。比如 n=97，d 只需要试到 10（10²=100>97）就会停，省去试 11~96 的麻烦。
内层 while n % d == 0: 不断除掉同一个因数。例如 n=12，d=2 时会依次除两次，得到 2,2 和剩余的 3。
最后 if n > 1: 处理漏网之鱼。比如分解 14，前半部分得到 2 后 n 变成 7，此时 d=3，3²=9>7，跳出外层循环，但 7 本身是质数，必须加进去。

新手容易犯的错误

忘记处理最后剩下的 n
有些同学循环结束后直接返回 factors，忘记判断 if n > 1。结果分解 14 只得到 [2]，少了 7。记住：凡是大于 √n 且没被分解的因子，一定是质数，必须单独加入。
把 d 的步长设为 2（只检查奇数）时搞混
如果为了提高效率跳过偶数，需要单独处理 2，然后从 3 开始步长 2。但初学者容易忘记先处理 2，或者 d 从 3 开始导致 2 被漏掉。建议早期先用“从 2 一个一个试”的简单方法，等熟练了再优化。
误以为需要提前准备质数列表
实际不用，因为合数因子会被更小的质数先除掉。比如 n=18，试 d=2 时除掉了 2，剩下 9；然后试 d=3 时就会除掉 3。虽然试了 d=4，但 18 里已经没有因子 4 了，不会出错，只是多试一次而已。对性能影响不大。
循环条件写成 d <= n
这样会试到结束，效率极低。用 d*d <= n 才是正确的高效方法。

完整可运行的示例程序

把上面代码复制到 Python 环境中就能运行。再补充一个交互式版本，让你输入任意整数试试：

def prime_factors(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

# 和用户互动
num = int(input("请输入一个大于1的整数："))
if num <= 1:
    print("1没有质因数。")
else:
    result = prime_factors(num)
    # 把列表转换成乘式字符串
    expression = " × ".join(str(x) for x in result)
    print(f"{num} = {expression}")

运行效果：

请输入一个大于1的整数：84
84 = 2 × 2 × 3 × 7

学完质因数分解，还可以学什么？

最大公约数与最小公倍数：用质因数分解法求最大公约数，就是取公共质因数的乘积；最小公倍数是取所有质因数的最高次幂相乘。
素数判断：质因数分解的循环技巧也可以用来判断一个数是不是素数——如果分解后列表长度只有 1，那它本身就是素数。
短除法：小学数学中那种写竖式分解的方法，实际上和代码的思路一模一样，只是写法不同。
高精度大数分解：等进入中学生信息学竞赛（CSP-J/S）后，你会遇到更大数字的分解，那时可以学习试除法的优化（比如只试 2 和奇数），甚至用到更高级的算法。

质因数分解就像数学世界里的“乐高说明书”，学会了它，很多看似复杂的数论问题都会变得清晰简单。试试自己写几个数分解一下吧！