优化非充裕资金算法

Question

我试图解决this Project Euler question：

一个完美的编号是针对其适当的除数 的总和正好等于号。例如，28的适当 除数的和将是1 + 2 + 4 + 7 + 14 = 28，这意味着28 是一个完美的数字。

如果数字n的合适除数之和为 小于n，则该数字n称为不足，如果该和超过n，则称该数字为富余。

由于12是最小的丰富数字，1 + 2 + 3 + 4 + 6 = 16，可以写成两个丰富数字 之和的最小数字是24.通过数学分析，它可以是表明所有大于28123的整数 可以写成两个丰富数字的总和。 但是，即使已知不能被 表示为两个丰富数字之和的最大数量小于此限制，该上限也不能通过分析 进一步减少。

查找所有不能写为 的正整数的总和两个丰富数字的总和。

我的解决办法：

#returns a list of the divisors of a given number 
def Divs(Number): 
    Divisors = [] 

    for i in range(2 , int(Number**0.5) + 1): 
     if Number % i == 0: 
      Divisors.append(i) 

    for q in range(len(Divisors)): 
     if Divisors[q] != (Number/Divisors[q]): 
      Divisors.append(Number/Divisors[q]) 

    Divisors.insert(0,1) 
    return Divisors 

#returns a list of abundant numbers up to and including the limit 
def AbList(limit): 
    Abundant = [] 

    for i in range(11,limit + 1): 
     if sum(Divs(i)) > i: 
      Abundant.append(i) 

    return Abundant 

#Finds the sum of all positive integers that cannot be written as the 
#sum of two abundant numbers... 
def AbSum(limit): 
    Abundant = AbList(limit) 
    NoAbSum = 0 
    for i in range(1 , limit): 
     AbSum = 0 
     x = 0 
     for x in Abundant: 
      if i - x in Abundant[:i]: 
       AbSum = 1 
       break 
     if AbSum == 0: 
      NoAbSum += i 
    return NoAbSum 

这花了我3.4 GHz处理器，约15分钟就可以解决，我正在寻找一种更好的方式。我不关心前两个功能，因为他们一起运行时间不到一秒钟。第三个功能是踢球者。它贯穿数字的范围，达到极限（在这种情况下，是20000），每一次都会遍历丰富的数字列表，从当前数字中减去每个数字，然后在丰富的列表中检查该答案数字。如果有匹配，循环会中断并再次尝试下一个数字，一直到极限。

我知道这样做有更好的方式，但我在编程方面有点新。我如何加快这个算法？

Answer 1

您正在测试每个数字介于1和极限（比方说30000）对每一个丰富的数字，所以你做大约30000 * 7428迭代;并且你正在检查结果是否在列表中，这是一个非常缓慢的操作 - 它检查列表中的每个项目，直到找到匹配项！

相反，你应该生成每个数字是两个丰富的数字的总和。最多需要7428 * 7428次迭代 - 如果执行得当（少提示：避免通过确保b总是> = a来检查a + b和b + a;并且像其他人所建议的那样，一定要停止当总和变得太大时）。将这些数字从limit以下的数字列表中标出，并对剩余的数字进行求和。

换句话说：

[... 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 ...] 

成为

[... 31, 0, 33, 34, 35, 0, 37, 0, 39, 0, 41, 0, 43 ...] 

---

编辑：用几分钟的实现播放后，我可以自信地说，if i - x in Abundant[:i]:是问题。在Project Euler的p23论坛上发布的第一个python解决方案本质上是您的算法的一个巧妙实现，唯一的主要区别是它使用数量充足的集合而不是列表。它在15秒内解决了Atom处理器上的问题;当我在15分钟后将其更改为使用列表时，仍未解决问题。

道德故事：x in list是SLOW。

不过，直接生成和会比减法和检查快。 :)

Answer 2

有一件事可以帮助您摆脱内循环，一旦大量的数字比你正在测试的大。

我也不太理解你的代码的此位：

for q in range(len(Divisors)): 
    if Divisors[q] != (Number/Divisors[q]): 
     Divisors.append(Number/Divisors[q]) 

一旦你验证了模数为0，这是一个约数。我不知道你为什么要做身份检查。

Answer 3

您的代码看起来好像可能会从映射，过滤器或列表理解中受益于那些for循环。

Answer 4

for x in Abundant: 
     if i - x in Abundant[:i]: 
      AbSum = 1 
      break 

注意，in表达这里需要O（ⅰ）时间，因此环是O（N²）。如果您使用set而不是list，则可以将此改进为O（n）。

Answer 5

您可以使用一个简单的数学方法：那种不能写成两个数目众多的总和所有数字的总和是所有数字减去的数字之和是可以写成作为2个丰富的数字的总和：

solution = sum(range(limit)) - sum(all_two_sums(abundant_numbers)) 

（sum(range(limit))也可以用数学简化，但除非你是高斯你可能不会发现它;-)）

你已经有一个列表数量丰富，所以创建可以将写成两个丰富数字的总和并且总和小于限制的那组数字相对容易。只要确保你没有重复的号码，一个Python set这样做。

Answer 6

让我们先搜索一下，找出最大的数字不可表示，因为两个丰富数字的总和实际上是20161。然后，我们可以用一个简单的集合成员测试来解决问题。另外，它运行得非常快。 :-)

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
from math import sqrt 

def d(n): 
    sum = 1 
    t = sqrt(n) 
    # only proper divisors; start from 2. 
    for i in range(2, int(t)+1): 
     if n % i == 0: 
      sum += i + n/i 
    # don't count the square root twice! 
    if t == int(t): 
     sum -= t 
    return sum 

limit = 20162 
sum = 0 
# it's a set, after all. sets are faster than lists for our needs. 
abn = set() 
for n in range(1, limit): 
    if d(n) > n: 
     abn.add(n) 
    # if the difference of the number we're examining and every number in the set 
    # is in the set, then the number is the sum of two abundant numbers. 
    # otherwise, we must add it to our sum in question. 
    if not any((n-a in abn) for a in abn): 
     sum += n 

在奔跑平均0.6463340939061518秒上在i5的基础上，timeit。