ProjectEuler#23解法与优化技巧分享

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《Project Euler #23 解法与优化技巧》，聊聊，希望可以帮助到正在努力赚钱的你。

本文详解 Project Euler 第 23 题的正确实现，重点剖析“动态检查是否为两丰数之和”这一思路中的关键漏洞——错误地将丰数本身纳入非丰数和集合，并指出实际有效上界应为 20161 而非 28123，从而修正长期被忽视的 995 偏差。

Project Euler 第 23 题要求：计算所有不能表示为两个丰数（abundant number）之和的正整数之和。其核心难点不在于高效求丰数，而在于对“可表示性”的判定逻辑是否严密。

你提供的 find_non_abd_sum 函数存在一个根本性逻辑错误：

if sum_of_divisors(n) > n:
    abd_lst.add(n)  # ✅ 正确：n 是丰数，加入集合
else:
    found = any((n-i) in abd_lst for i in abd_lst)
    if not found:
        sum += n  # ❌ 错误：此处仅跳过了丰数，但未排除「非丰数却仍可表为两丰数之和」的情况！

问题在于：else 分支只处理了 非丰数（即 sum_of_divisors(n) <= n），但题目要求排除的是 所有能写成两丰数之和的数——无论它自身是否丰数！
例如：

• 24 = 12 + 12 → 24 是丰数，但它必须被排除（因它是两丰数之和）；
• 30 = 12 + 18 → 30 是丰数，同样必须被排除；
• 945 是第一个奇丰数，但它本身不是答案的一部分，但它的存在意味着：任何 ≥ 945+12 = 957 的数，若能拆成两个丰数，就不可计入答案。

而你的逻辑中，n 只有在「非丰数」的前提下才检查是否可拆分；一旦 n 是丰数（如 12、18、20、945），它直接跳过判定，被默认加入答案——这正是多出 12+18+20+945 = 995 的根源！

✅ 正确做法是：对每个 n（1 到上限），无条件检查它能否表示为两个已知丰数之和；只有当 n 既不是丰数，也不能拆成两个已有丰数之和时，才累加。

此外，权威数学结论（Wolfram MathWorld 等）指出：所有大于 20161 的整数均可表示为两个丰数之和，因此本题实际有效上界是 20161，而非题目中保守给出的 28123。使用 28123 不影响正确性，但会显著增加无效计算量（约多循环 8000 次），且易掩盖逻辑缺陷。

以下是修正后的完整实现（含高效约数和函数与清晰主逻辑）：

def sum_proper_divisors(n):
    """返回 n 的真因子（proper divisors）之和，即除自身外的所有正因子之和"""
    if n <= 1:
        return 0
    total = 1
    # 只需遍历到 sqrt(n)
    i = 2
    while i * i <= n:
        if n % i == 0:
            total += i
            if i != n // i:  # 避免完全平方数重复计数
                total += n // i
        i += 1
    return total

def is_abundant(n):
    return sum_proper_divisors(n) > n

def solve_euler_23(limit=20162):
    abundant_set = set()
    total = 0

    for n in range(1, limit):
        # 先判断 n 是否为丰数，若是则加入集合
        if is_abundant(n):
            abundant_set.add(n)

        # 关键：无论 n 是否丰数，都检查它能否表示为两个丰数之和
        can_be_sum = False
        for a in abundant_set:
            if a > n // 2:  # 避免重复检查（a ≤ b ⇒ a ≤ n/2）
                break
            if (n - a) in abundant_set:
                can_be_sum = True
                break

        if not can_be_sum:
            total += n

    return total

# 执行
print(solve_euler_23())  # 输出：4179871

? 关键改进点总结：

• 逻辑修正：移除 else 分支，对每个 n 统一执行“是否可表为两丰数之和”的判定；
• 效率优化：内层循环只需检查 a ≤ n//2，因若 a + b = n 且 a ≤ b，则 a ≤ n/2；
• 边界确认：采用 limit = 20162（覆盖 1~20161），符合数学最优上界；
• 鲁棒性增强：sum_proper_divisors 正确处理 n=1 边界，并避免平方根处重复加数。

运行该代码将精确输出 Project Euler 官方答案：4179871，彻底解决 995 偏差问题。此解法兼具正确性、可读性与工程实用性，是理解本题深层逻辑的理想范本。

终于介绍完啦！小伙伴们，这篇关于《ProjectEuler#23解法与优化技巧分享》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！