如何获取大数17309205的全部4元因数组合并修复Python实现问题

原代码问题分析 #

• 递归逻辑提前终止：遍历到第一个符合条件的因数就直接return，没有收集所有可能的因数组合
• 未限制输出元素数量：没有控制最终返回的组合必须是4个元素
• 存在大量冗余计算：遍历范围是2到目标数本身，实际因数只需要遍历到目标数的平方根即可覆盖所有可能
• 未做去重处理：没有限制元素非降序排列，会生成大量顺序不同但元素完全一致的重复组合

优化实现方案 #

实现思路：

1. 先预生成目标数的所有正因数，减少后续判断开销
2. 用回溯法按非降序选择元素，保证最终组合不会重复
3. 当已选元素个数为3时，直接计算剩余需要的数是否符合要求，减少递归层数

import math

TARGET = 17309205

# 预获取所有正因数
def get_all_factors(n):
    factors = set()
    for i in range(1, int(math.isqrt(n)) + 1):
        if n % i == 0:
            factors.add(i)
            factors.add(n // i)
    return factors

all_factors = get_all_factors(TARGET)
sorted_factors = sorted(all_factors)
result = []

# 回溯找4元非降序组合
def backtrack(start_idx, path, remain_val):
    selected_cnt = len(path)
    # 已经选了3个，剩下1个直接判断合法性
    if selected_cnt == 3:
        if remain_val >= path[-1] and remain_val in all_factors:
            path.append(remain_val)
            result.append(tuple(path))
            path.pop()
        return
    # 按非降序选下一个因数
    for i in range(start_idx, len(sorted_factors)):
        current_factor = sorted_factors[i]
        if current_factor > remain_val:
            break
        if remain_val % current_factor != 0:
            continue
        path.append(current_factor)
        backtrack(i, path, remain_val // current_factor)
        path.pop()

backtrack(0, [], TARGET)

# 按要求格式输出
for combo in result:
    print("{" + ",".join(map(str, combo)) + "}")

输出示例 #

运行后会输出所有符合要求的组合，前几条展示如下：

{1,1,1,17309205}
{1,1,3,5769735}
{1,1,5,3461841}
{1,1,9,1923245}
...

内容的提问来源于stack exchange，提问作者A Din