唯一分解定理 - 五级 | C++ & Algorithm 编程研习社

拆解数字的积木：唯一分解定理与质因数分解

你有没有玩过积木？一块复杂的造型，拆开来看就是几种基本形状的积木拼起来的。数字的世界里也有这样的“基本积木”，那就是质数。任何一个大于1的整数，都可以被拆成若干个质数相乘的形式，而且拆法只有一种（不计顺序）——这就是唯一分解定理，也叫算术基本定理。

比如 30 = 2 × 3 × 5，84 = 2 × 2 × 3 × 7 = 2² × 3 × 7。这些质数就像积木的“零件”，每个合数都能拆成这样的零件组合。学会这个“拆解魔法”，你不仅能看懂数字的构成，还能用它来解决实际问题，比如求最大公因数、判断数字是否互质，甚至理解网上支付时用的加密技术（RSA算法）。

一、先认识两种“数字积木”：质数与合数

质数：只有1和它本身两个因数。比如 2、3、5、7、11……
合数：除了1和它本身还有其他因数。比如 4、6、8、9、10……

唯一分解定理告诉我们：每个大于1的整数，要么本身就是质数（不用拆），要么就是几个质数相乘得到的。而且拆出来的质数就像积木的“规格”，谁也不能多一个或少一个。

生活中的例子：你有30颗糖果，想分给小朋友们，要求每人分到的糖果数相同，且不能有人拿到1颗。那么你可以让2人每人15颗、3人每人10颗、5人每人6颗……但继续分到最小时，每个人就只能拿到2颗、3颗或5颗了——这些“最小份”就是质数。

二、怎么把一个数拆成质因数的乘积？（质因数分解）

最直接的方法叫试除法：从最小的质数2开始，检查它能不能整除这个数。如果能，就把它记下来，然后用商继续试除同一个数，直到不能整除，再换下一个数。

关键原理：如果一个合数有因数，那么它一定有一个不大于它的平方根的因数。所以我们只需要试除到 √n 就够了，能省下很多时间。

用Python写出来就是这样：

def factorize(n):
    factors = []          # 存储质因数的列表
    d = 2                 # 从最小的质数开始试除
    while d * d <= n:     # 只需要试到根号n
        while n % d == 0: # 如果能整除，说明d是一个质因子
            factors.append(d)
            n //= d
        d += 1
    if n > 1:             # 如果最后剩下的n大于1，它本身也是质数
        factors.append(n)
    return factors

# 测试
print(factorize(84))   # 输出 [2, 2, 3, 7]
print(factorize(97))   # 输出 [97] (质数)

运行过程手把手看（以84为例）：

初始 n=84，d=2。
2²=4 ≤ 84？是。84 % 2 == 0，所以添加2，n变成42；再次试除：42 % 2 == 0，再添加2，n变成21；21 % 2 != 0，跳出内层循环。d+1=3。
3²=9 ≤ 21？是。21 % 3 == 0，添加3，n变成7；7 % 3 != 0。d+1=4。
4²=16 ≤ 7？否。跳出外层循环。
最后 n=7 > 1，添加7。得到 [2, 2, 3, 7]。

三、为什么用试除法时合数除数不会“捣乱”？

你有没有想过：当 d=4 时，4 是个合数，但 n 已经被2除干净了，所以 n 不可能被4整除。这就保证了只有质数除数才会成功，我们不需要特意跳过合数。

比如 n=60：先被2除到15，然后 d=3 时把15变成5，d=4 时 4²=16 > 5，跳出，最后添加5。我们永远不会碰到“4整除”的情况。

四、新手常犯的错误

忘记处理最后剩下的 n
如果 n 在循环结束后大于1，说明它是一个大于 √n 的质因子。如果不写 if n > 1: factors.append(n)，就会漏掉这个因子。比如 n=10：循环中 d=2 把10变成5，d=3 时 3²=9 > 5 跳出，最后 n=5 > 1，必须添加5，否则结果只有[2]。
循环条件写成 d <= n 而不是 d*d <= n
这样会多算很多步，虽然结果也正确，但效率极低。比如 n=997（质数），用 d*d<=n 只需试到31，用 d<=n 要试到997。
整数除法搞混
n //= d 是整数除法（地板除），如果写成 n /= d，n 会变成浮点数，后面取余运算会出问题。
分解结果顺序
我们得到的因子是递增的，如果希望按指数形式输出（比如 84 = 2² × 3 × 7），需要额外统计每个质数出现的次数。

五、完整可运行的示例（含输入输出）

下面这个程序让用户输入一个数，然后输出它的质因数分解结果（带指数）：

def prime_factors_with_exponent(n):
    """
    返回一个字典，键为质因数，值为指数
    """
    factors_count = {}    # 空字典，用来统计每个质数出现的次数
    d = 2                 # 从2开始试除
    while d * d <= n:     # 试除到根号n
        while n % d == 0:
            # 如果d已经在字典中，就加1；否则初始化为1
            factors_count[d] = factors_count.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:             # 处理最后剩下的质数
        factors_count[n] = factors_count.get(n, 0) + 1
    return factors_count

# 让用户输入一个数
num = int(input("请输入一个大于1的整数："))

# 调用函数得到质因数统计
result = prime_factors_with_exponent(num)

# 构造输出字符串，例如 84 = 2^2 * 3 * 7
parts = []
for prime, exponent in result.items():
    if exponent == 1:
        parts.append(str(prime))
    else:
        parts.append(f"{prime}^{exponent}")
output = " * ".join(parts)

print(f"{num} = {output}")

# 运行示例：
# 输入 84
# 输出 84 = 2^2 * 3 * 7
#
# 输入 97
# 输出 97 = 97
#
# 输入 1024
# 输出 1024 = 2^10

尝试自己跑一下，输入你的生日、学号或者喜欢的数字，看看它由哪些“积木”组成！

六、生活中的更多例子

零花钱：你每星期有12元零花钱，你想把它换成最小面额的硬币（假设只有2元、3元、5元硬币）。12 = 2×2×3，所以可以用2个2元硬币和1个3元硬币（或者4个2元+1个? 哦不行，因为只有2、3、5）。质因数分解帮你找到所有可能的组合。
排队分组：学校有48人参加合唱比赛，想分成人数相同的小组，每组人数必须超过1。那么小组人数可以是48的因数：2、3、4、6、8、12、16、24。这些因数其实都是由48的质因数 2⁴×3 组合出来的（2的0到4次方乘以3的0或1次方）。
密码学：RSA加密算法之所以安全，就是因为把一个很大的数（比如几百位）分解成两个大质数相乘非常困难，但反过来求乘积却很简单。这就像知道锁头（合数）容易，但不知道钥匙（质因数）就很难打开。

七、相关知识点指引

掌握了唯一分解定理，你可以继续探索：

最大公因数：用质因数分解法求两个数的公因数，比如 84=2²×3×7，60=2²×3×5，公因数是 2²×3=12。
最小公倍数：每个质数取最高指数相乘，84和60的最小公倍数是 2²×3×5×7=420。
因数个数：一个数 n = p₁^a × p₂^b × ... ，它的因数个数是 (a+1)(b+1)...（比如 84=2²×3×7，因数个数为 (2+1)(1+1)(1+1)=12）。
更大数的分解：当数字大到10^12时，试除法会变慢，可以用更高效的算法如 Pollard Rho。但在小学和初中阶段，试除法足够应对几百以内的数了。

拆解数字的“积木”，从此数论不再是难题！如果你对密码学感兴趣，可以进一步了解“大数质因数分解”为什么这么难，以及RSA算法是怎么利用这个难题保护我们的网络信息的。

例题精讲