Python质因数分解详解（从零开始掌握质因数分解算法）

算法思路

我们可以用以下简单逻辑来实现质因数分解：

1. 从最小的质数2开始尝试除以目标数。
2. 如果能整除，就把这个因子记录下来，并继续用商做下一次分解。
3. 当不能整除时，尝试下一个可能的因子（3, 5, 7...）。
4. 重复上述过程，直到剩下的数变成1。

Python代码实现

下面是一个清晰、高效的质因数分解函数：

def prime_factorization(n):    """返回 n 的质因数列表"""    factors = []    divisor = 2        while n > 1:        while n % divisor == 0:            factors.append(divisor)            n //= divisor        divisor += 1                # 优化：如果 divisor 的平方大于 n，说明 n 本身是质数        if divisor * divisor > n and n > 1:            factors.append(n)            break                return factors# 测试示例print(prime_factorization(12))   # 输出: [2, 2, 3]print(prime_factorization(30))   # 输出: [2, 3, 5]print(prime_factorization(17))   # 输出: [17]

代码解释

- 我们初始化一个空列表 factors 来存储质因数。

- 从 divisor = 2 开始，不断尝试能否整除 n。

- 每次成功整除后，将因子加入列表，并更新 n = n // divisor。

- 当 divisor * divisor > n 且 n > 1 时，说明剩下的 n 本身就是质数，直接加入结果即可。这是一个重要的性能优化，避免不必要的循环。

为什么学习质因数分解？

掌握Python质因数分解不仅有助于理解基本的数学概念，还能提升你的编程逻辑能力。它在密码学、数论、算法竞赛等领域都有广泛应用。对于初学者学Python来说，这是锻炼循环、条件判断和函数编写的好练习。

小结

通过本篇Python编程教程，你已经学会了如何用Python实现一个高效、易读的质因数分解算法。试着修改代码，比如让它返回字典形式（质因数及其出现次数），或者处理更大的数字，进一步巩固所学知识！