Python质因数分解 - 五级 | C++ & Algorithm 编程研习社

把数字拆成“最小积木块”——Python质因数分解

你有没有玩过乐高？一个巨大的城堡模型，其实是由一个个基础的小积木块搭起来的。数学里的“质因数分解”就像做相反的事：把一个合数（不是质数的数）拆成几个不能再拆的素数（又称质数）相乘的形式。比如 12 = 2 × 2 × 3，2 和 3 就是 12 的质因数。有了这个“拆解”，我们可以轻松找到两个数的最大公因数、最小公倍数，还能理解密码学里的一些秘密哦！

1. 先认识几个“积木块”概念

质数（素数）：只能被 1 和它本身整除的数，比如 2、3、5、7、11……它们是最小的“积木块”，不能再拆了。
合数：除了 1 和本身，还能被其他数整除，比如 4、6、8、9、12……合数都能拆成几个质数相乘。
质因数：就是那些组成合数的质数因子。比如 12 的质因数有 2 和 3（注意 2 出现了两次）。

生活类比：你有一包 60 粒的积木，你想知道它是由哪些颜色的基础积木组成的。每次你拿出一种颜色的积木，数一数有多少个，直到袋子变空。质因数分解就是“数出每种颜色积木的数量”——只不过颜色对应不同的质数。

2. 怎么用 Python 拆？——试除法的思路

我们从一个很小的质数 2 开始，不停地用这个质数去除目标数，如果除得尽，就记下这个质数，然后让目标数变小；如果除不尽，就换下一个质数（比如 3、5、7……）。一直除到目标数变成 1 为止。注意，同一个质数可能会重复出现，比如 12 里有两个 2，所以要一直试除同一质数直到除不尽。

优化小技巧：我们不需要试除到 n 那么大，只要试到 n 的平方根就够了。因为如果一个合数 n 有大于 sqrt(n) 的质因数，那么它一定也有一个小于等于 sqrt(n) 的质因数。这样能大大加快速度。

代码拆解（保留原有代码，添加注释）：

def prime_factorization(n):
    factors = []              # 用来存所有质因数的列表
    d = 2                     # 从最小的质数2开始试
    while d * d <= n:         # 只要d的平方 <= n，就继续试
        while n % d == 0:     # 如果d能整除n
            factors.append(d) # 记下这个因子d
            n //= d           # 把n缩小为n除以d后的值
        d += 1                # 试下一个数（注意：这里d可能是合数，但没关系）
    if n > 1:                 # 最后剩下的n如果是大于1的质数，也要记下
        factors.append(n)
    return factors

print(prime_factorization(12))    # 输出 [2, 2, 3]
print(prime_factorization(100))   # 输出 [2, 2, 5, 5]
print(prime_factorization(97))    # 输出 [97] (97本身是质数)

像用筛子筛面粉：先用 2 号筛子筛，筛出所有“2”的因子；换 3 号筛子，筛出“3”的因子……直到筛子孔比剩下的面粉粒还大，剩下的那一粒面粉本身就是一个质因数。

3. 生活中的例子：分糖果、分组、密码学

分糖果：你有 60 块糖，想平均分给小朋友，但又不知道最多可以分给多少人。先分解 60 = 2 × 2 × 3 × 5，那么所有可能的份数就是这些质因数的任意组合（1,2,3,4,5,6,10,12,15,20,30,60）。比如分给 12 个小朋友，每人 5 块，因为 12×5=60。
分组：班级有 48 人，要分成人数相同的小组。48 = 2 × 2 × 2 × 2 × 3，所以可以分成 2人组、3人组、4人组、6人组……理解质因数能帮你快速找到所有分组方式。
密码学：RSA 加密算法基于“大数分解很难”。比如几百位的合数想拆成质因数，用电脑也要算很久，所以我们可以用它做加密。

4. 新手最容易犯的 3 个错误

忘记处理最后剩下的 n
如果输入本身就是质数，比如 97，循环结束后 n 还是 97，没有加入 factors 就会漏掉。一定要加 if n > 1: factors.append(n)。
循环条件写成 while d <= n
这样会浪费很多时间，尤其是对很大的数（比如 1000000 要试除 1000000 次）。正确做法是 while d * d <= n，只试到平方根。
误把 1 当作质因数
1 不是质数也不是合数，分解时不需要加 1。如果用户输入 1，函数应该返回空列表。可以在开头加个判断：
```
if n <= 1:
    return []  # 1 没有质因数
```

5. 完整可运行示例（多测试几个数）

下面是一个更完整的代码，包括了输入处理和多个测试：

def prime_factorization(n):
    if n <= 1:
        return []              # 1 和负数没有质因数
    factors = []               # 存储质因数的列表
    d = 2                      # 从质数2开始试
    while d * d <= n:          # 只检查到平方根
        while n % d == 0:      # 如果能整除
            factors.append(d)  # 记录因子
            n //= d            # 缩小n
        d += 1                 # 试下一个数
    if n > 1:                  # 剩下的n如果是质数
        factors.append(n)
    return factors

# 测试几个数
test_numbers = [12, 100, 97, 60, 1, 84, 360]
for num in test_numbers:
    result = prime_factorization(num)
    print(f"{num} 的质因数：{result}")

输出：

12 的质因数：[2, 2, 3]
100 的质因数：[2, 2, 5, 5]
97 的质因数：[97]
60 的质因数：[2, 2, 3, 5]
1 的质因数：[]
84 的质因数：[2, 2, 3, 7]
360 的质因数：[2, 2, 2, 3, 3, 5]

6. 想一想，然后去探索更多

质因数分解像一个“数字拆解器”，拆出来的积木块能帮我们做很多事。

想一想：60 = 2 × 2 × 3 × 5，那么和 60 有相同质因数的数还有哪些？（提示：比如 30、120、180……只要这些质因数的指数不同。）
相关知识点：
- 最大公约数和最小公倍数：把两个数分解质因数，取公共的质因数乘起来就是最大公约数，取所有质因数（每个取最大次数）乘起来就是最小公倍数。
- 判断质数：用类似的试除法可以写一个函数判断一个数是不是质数。
- 约分：分子分母同时除以它们的最大公约数，就是约分。而最大公约数由质因数分解轻松得到。

你可以试着修改代码，让它输出“2^3 × 3^2 × 5”这种指数形式，更接近数学表达。质因数分解是打开数论世界的一把钥匙，多练习，你会发现数字的秘密越来越有趣！