Project Euler #23 答案错误

Question

我刚刚完成了项目Euler第23题的解法，题目是这样的：

完美数是指一个数的所有真因子（除了它自己）加起来正好等于这个数。例如，28的真因子是1、2、4、7和14，它们的和是1 + 2 + 4 + 7 + 14 = 28，这说明28是一个完美数。

如果一个数n的真因子之和小于n，我们称这个数为缺陷数；如果真因子之和大于n，则称为丰盈数。

12是最小的丰盈数，因为1 + 2 + 3 + 4 + 6 = 16，而可以表示为两个丰盈数之和的最小数是24。通过数学分析可以证明，所有大于28123的整数都可以表示为两个丰盈数之和。不过，虽然已知最大的不能表示为两个丰盈数之和的数小于这个限制，但通过分析无法进一步降低这个上限。

找出所有不能表示为两个丰盈数之和的正整数的总和。

这是我的解法：

from math import sqrt
def divisors(n):
    for i in range(2, 1 + int(sqrt(n))):
        if n % i == 0:
            yield i
            yield n / i

def is_abundant(n):
    return 1 + sum(divisors(n)) > n

abundants = [x for x in range(1, 28123 + 1) if is_abundant(x)]
abundants_set = set(abundants)

def is_abundant_sum(n):
   for i in abundants:
       if i > n:  # assume "abundants" is ordered
         return False
       if (n - i) in abundants_set:
           return True
   return False

sum_of_non_abundants = sum(x for x in range(1, 28123 + 1) if not is_abundant_sum(x))
print(sum_of_non_abundants)

我的答案是：3906313

我的代码解释： divisors这个生成器基本上返回一个整数的所有非平凡因子，但不保证顺序。它会从1循环到n的平方根，并返回因子及其商。接下来的函数is_abundant实际上检查n的因子之和是否小于n，如果小于则返回False，否则返回True。接下来是列表abundants，它保存了从1到28123的所有丰盈数，而abundants_set和abundants类似，但它是一个集合而不是列表。下一个函数是is_abundant_**sum**，它检查传入的和是否本身是丰盈数，最后打印出那些不是is_abundant_sum的数的总和。

我哪里做错了？我的代码有什么问题？

任何帮助都将不胜感激。

Answer 1

这个 divisors 生成器在计算的时候，把因子 f 计算了两次，特别是当 f 是 f**2 的时候。这个问题会影响到计算出来的丰数列表。