### Python 实现正整数分解质因数 以下是基于引用中的方法以及标准实现方式来完成此功能的代码： #### 方法一：迭代法 这种方法利用了质数的特性，逐步尝试将当前数值除以其最小可能的因子。 ```python def factorize(n): factors = [] divisor = 2 # 初始质数为2 while n > 1: while n % divisor == 0: # 如果可以整除，则记录该因子 factors.append(divisor) n //= divisor divisor += 1 # 尝试下一个可能的因子 return factors # 主程序部分 if __name__ == "__main__": num = int(input("输入一个正整数: ")) result = factorize(num) output = f"{num}=" + "*".join(map(str, result)) # 格式化输出 print(output) ``` 上述代码实现了从小到大提取所有质因数的功能[^2]。对于输入 `90` 的情况，其输出将是 `90=2*3*3*5`。 --- #### 方法二：优化版迭代法 为了提高效率，我们可以在每次寻找因子时仅考虑小于等于平方根的部分，并在最后处理剩余的大于平方根的单一质数（如果有）。 ```python import math def optimized_factorize(n): factors = [] divisor = 2 while divisor * divisor <= n: # 只需检查至sqrt(n) while (n % divisor) == 0: factors.append(divisor) n //= divisor divisor += 1 if n > 1: # 剩余大于sqrt(n)的质数直接加入列表 factors.append(n) return factors # 主程序部分 if __name__ == "__main__": num = int(input("输入一个正整数: ")) result = optimized_factorize(num) output = f"{num}=" + "*".join(map(str, result)) print(output) ``` 这段代码的时间复杂度接近 O(√n)[^3]，相比简单枚举更高效。 --- #### 方法三：递归法 递归是一种简洁而优雅的方式来解决问题，尽管它可能会稍微增加栈空间消耗。 ```python def recursive_factorize(n, k=2): # 默认从最小质数2开始测试 if n < 2: # 边界条件 return [] elif n % k == 0: # 找到了一个因子 return [k] + recursive_factorize(n // k, k) else: # 继续查找更大的因子 return recursive_factorize(n, k + 1) # 主程序部分 if __name__ == "__main__": num = int(input("输入一个正整数: ")) result = recursive_factorize(num) output = f"{num}=" + "*".join(map(str, result)) print(output) ``` 递归版本同样能够正确地分解任何给定的正整数为其质因数组合[^4]。 --- ### 总结 以上三种方法均能有效解决正整数分解成质因数的问题。其中，**优化版迭代法**因其较高的性能表现，在实际应用中更为推荐；而对于教学目的或者理解算法逻辑而言，**递归法**则提供了清晰直观的学习路径。