我找不到哪里做错了：(

Question

我在用python处理euler问题23。对于这个问题，我必须求出任何数的和<；28124，它不能由两个丰富数的和构成。富足数是小于其自身固有因子之和的数。你知道吗

我的回答是：https://gist.github.com/anonymous/373f23098aeb5fea3b12fdc45142e8f7

from math import sqrt

def dSum(n): #find sum of proper divisors
    lst = set([])
    if n%2 == 0:
        step = 1
    else:
        step = 2
    for i in range(1, int(sqrt(n))+1, step):
        if n % i == 0:
            lst.add(i)
            lst.add(int(n/i))
    llst = list(lst)
    lst.remove(n)
    sum = 0
    for j in lst:
        sum += j
    return sum

#any numbers greater than 28123 can be written as the sum of two abundant numbers.
#thus, only have to find abundant numbers up to 28124 / 2  = 14062

abnum = [] #list of abundant numbers
sum = 0 
can = set([])

for i in range(1,14062):
    if i < dSum(i):
        abnum.append(i)

for i in abnum:
    for j in abnum:
        can.add(i + j)

print (abnum)
print (can)

cannot = set(range(1,28124))
cannot = cannot - can
cannot = list(cannot)
cannot.sort ()

result = 0

print (cannot)

for i in cannot:
    result += i

print (result)

我的答案是31501，这是错的。你知道吗

我在谷歌上搜索了答案，答案应该是4179871。你知道吗

答案之间有100万个差异，所以这意味着我要删除不能写成两个丰富数字之和的数字。但是当我重新阅读代码时，逻辑上看起来很好。。。你知道吗

请不要绝望

Answer 1

只是为了获得一些经验，你真的应该看看理解和利用内置的（而不是隐藏它们）：

在dSum()（也可以简化）之外的循环可以如下所示：

import itertools as it

abnum = [i for i in range(1,28124) if i < dSum(i)]
can = {i+j for i, j in it.product(abnum, repeat=2)}

cannot = set(range(1,28124)) - can
print(sum(cannot)) # 4179871

Answer 2

有几种方法可以改进代码。你知道吗

首先，这里有一个更紧凑的dSum版本，它非常接近您的代码。运算符通常比函数调用快，因此我使用** .5而不是调用math.sqrt。我使用条件表达式而不是if...else块来计算步长。我使用内置的sum函数而不是for循环来累加除数；此外，我还使用整数减法从总数中删除n，因为这比调用set.remove方法更有效。你知道吗

def dSum(n):
    lst = set()
    for i in range(1, int(n ** .5) + 1, 2 if n % 2 else 1):
        if n % i == 0:
            lst.add(i)
            lst.add(n // i)
    return sum(lst) - n

但是，我们不需要在这里使用集合。我们可以在找到除数对时把它们加起来，如果我们小心不要把任何除数加两次的话。你知道吗

def dSum(n):
    total = 0
    for i in range(1, int(n ** .5) + 1, 2 if n % 2 else 1):
        if n % i == 0:
            j = n // i
            if i < j:
                total += i + j
            else:
                if i == j:
                    total += i
                break
    return total - n

这会稍微快一点，并且使用更少的RAM，但会增加代码复杂性。然而，有一种更有效的方法来解决这个问题。你知道吗

与其单独寻找每个数字的除数（因此也就是除数和），不如使用筛选方法，找到所需范围内所有数字的除数。下面是一个简单的例子。你知道吗

num = 28124

# Build a table of divisor sums.
table = [1] * num
for i in range(2, num):
    for j in range(2 * i, num, i):
        table[j] += i

# Collect abundant numbers
abnum = [i for i in range(2, num) if i < table[i]] 
print(len(abnum), abnum[0], abnum[-1])

输出

6965 12 28122

如果我们需要求一个非常大的num的除数和，一个好的方法是求每个数的素数幂因子，因为有一种有效的方法可以从素数幂因子分解计算除数和。然而，对于这么小的数字，节省的时间并不足以保证额外的代码复杂性。（但如果您好奇的话，我可以添加一些素数幂筛代码；对于查找所有数字的除数和<；28124，素数幂筛技术的速度大约是上述代码的两倍）。你知道吗

AChampion的答案展示了一种非常简洁的方法，可以找到不能写成两个丰富数之和的数之和。但是，它有点慢，主要是因为它在abnum中循环遍历所有丰富的数字对。这里有一个更快的方法。你知道吗

def main():
    num = 28124

    # Build a table of divisor sums. table[0] should be 0, but we ignore it.
    table = [1] * num
    for i in range(2, num):
        for j in range(2 * i, num, i):
            table[j] += i

    # Collect abundant numbers
    abnum = [i for i in range(2, num) if i < table[i]] 
    del table

    # Create a set for fast searching
    abset = set(abnum)
    print(len(abset), abnum[0], abnum[-1])

    total = 0
    for i in range(1, num):
        # Search for pairs of abundant numbers j <= d: j + d == i 
        for j in abnum:
            d = i - j
            if d < j:
                # No pairs were found
                total += i
                break
            if d in abset:
                break

    print(total)

if __name__ == "__main__":
    main()

输出

6965 12 28122
4179871

这段代码在运行python3.6.0的32位单核2GHz旧机器上运行大约2.7秒。在Python2上，大约快了10%；我认为这是因为列表理解在Python2中开销较小（在当前范围内运行而不是创建新范围）。你知道吗