优化非丰富和算法

Question

我正在尝试解决这个项目欧拉问题:

完美数字是一个数字,其正确除数的总和恰好等于数字.例如,28的适当除数之和为1 + 2 + 4 + 7 + 14 = 28,这意味着28是一个完美数.

如果n的适当除数之和小于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-something),每次,它运行在大量数字列表中,从当前数字中减去每个数字,然后根据丰富的列表检查该答案数字.如果匹配,则循环中断并再次尝试下一个数字,一直到极限.

我知道必须有一个更好的方法来做这个,但我对编程有些新意.我怎样才能加速这个算法？

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处理器上的问题; 当我改变它使用列表,十五分钟后,它仍然没有解决问题.

故事的道德:x in list是慢的.

但是,直接生成总和比减去和检查要快.:)

Answer 2

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

注意,in这里的表达式需要O(i)时间,因此循环是O(n²).如果使用a set而不是a,可以将其改进为O(n)list.