项目欧拉#23 - Python非丰富的总和

Question

我一直在努力Project Euler #23.

这是任务:

问题23

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

如果n的适当除数之和小于n,则数n被称为不足,如果该和超过n,则称其为n.

由于12是最小的有限数,1 + 2 + 3 + 4 + 6 = 16,可以写成两个有限数之和的最小数是24.通过数学分析,可以显示所有整数大于28123可以写成两个数字的总和.然而,即使已知不能表示为两个充裕数的总和的最大数量小于该限制,也不能通过分析进一步减小该上限.

找到所有正整数的总和,这些正整数不能写为两个数字的总和.

这是我的代码:

import math

def getDivisors(num):
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    return total

def isAbundant(num):
    if (getDivisors(num) > num):
        return True
    else:
        return False

abundentNums = []
for x in range (0,28124):
    if (isAbundant(x)):
        abundentNums.append(x)
del abundentNums[0]

sums = [0]*28124
for x in range (0, len(abundentNums)):
    for y in range (x, len(abundentNums)):
            sumOf2AbundantNums = abundentNums[x]+abundentNums[y]
            if (sumOf2AbundantNums<= 28123):
                if (sums[sumOf2AbundantNums] == 0):
                    sums[sumOf2AbundantNums] = sumOf2AbundantNums

total = 0
for x in range (1,len(sums)):
    if (sums[x] == 0):
        total +=x

print('\n', total)

我得到的总价值是4190404.正确的答案是4179871.我花了一个小时查看我的代码,但我无法找到错误.我应该更改什么来纠正错误？我的答案很接近.提前致谢

PS.我是python的新手.运行时间为25秒,任何优化也都有用.

Answer 1

你的getDivisors功能不正确.它不计算平方数的根除数(例如,if num=25,它将返回1).这是一个更正版本:

def getDivisors(num):
    if num==1:
        return 1
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    if n**2==num:
        total+=n
    return total

使用此功能,我得到了所需的结果4179871.