Python-Maths Project Euler P23

Question

def isAbundant(testNum):
    total = 1
    divisor = 2 
    while divisor < (testNum/2  + 1):
        if(testNum%divisor == 0):
            total = total + divisor
        divisor = divisor + 1   
    if total > testNum:
        result = True
    else:
        result = False
    return result

#create a list of abundant numbers
i = 12
listOfAbunNo = []
sums = []
while i < 28112:
    if isAbundant(i) == True:
        listOfAbunNo.append(i)
    i = i+1 
    print(i)
# create list of sums of Abundant numbers
i = 0
print(len(listOfAbunNo))
while i < len(listOfAbunNo):
    j = i                       # i and j are abundant numbers (indexes) to sum
    while j <len(listOfAbunNo):  
        sums.append(listOfAbunNo[i]+listOfAbunNo[j])
        j=j+1
    i = i+1
#remove duplicates 
sums.sort() 
i = 1
while i<len(sums):
    if (sums[i-1] == sums[i]):
        sums.remove(sums[i-1])
    else:
        i = i + 1
#calc total
print(str(sum[12,28111] - sum(sums)))

这是我为问题https://projecteuler.net/problem=23编写的代码，对吗？我该如何优化它呢？

问题完美数是指其真约数之和恰好等于该数的数。例如，28的适当因子的和将是1+2+4+7+ 14 = 28，这意味着28是一个完美的数字。

如果一个数n的真因子之和小于n，则称其为亏数；如果这个数之和超过n，则称其为富足数。

由于12是最小的富足数，1+2+3+4+6= 16，所以可以写成两个富足数之和的最小数是24。通过数学分析可以看出，所有大于28123的整数都可以写成两个富足数字的和。然而，这个上限不能通过分析进一步降低，即使我们知道不能表示为两个富足数之和的最大数小于这个上限。

求出所有不能写成两个富足数之和的正整数之和。

Answer 1

是正确的吗？

是-除了最后一步，用print(str(sum[12,28111] - sum(sums)))计算总数不起作用：

1. sums包含所有的合成数，也包含大于28112的合成数。试试print(max(sums))，你会得到56220。所以你不能简单地将所有这些数字相加，其中许多数字不应该计入总数。
2. 你应该提供“所有正整数(...)”的和。因此您应该从1开始，而不是12.
3. sum[12, 28111]无效的Python语法，请尝试使用sum(range(12, 28111))

您可以执行以下最后一步:生成一个包含所有非复合数字的列表，即您想要相加的数字，然后对这些数字求和：

non_composites = sum([i for i in range(1, 28112) if i not in sums])
print(str(non_composites))

以及如何对其进行优化？

删除重复项：您可以优化‘删除重复项’-part：

#remove duplicates 
sums.sort() 
i = 1
while i<len(sums):
    if (sums[i-1] == sums[i]):
        sums.remove(sums[i-1])
    else:
        i = i + 1

可以写得更有pythonic风格(也更快)，比如

#remove duplicates 
sums = list(set(sums))

这将使sums成为一个set，删除它的所有重复项，然后再次使其成为一个列表。

isAbundant-function:代替

if total > testNum:
    result = True
else:
    result = False
return result

你可以写

return total > testNum

list of sums：这部分也可以简化为

# create list of sums of Abundant numbers
i = 0
print(len(listOfAbunNo))
while i < len(listOfAbunNo):
    j = i
    while j <len(listOfAbunNo):  
        sums.append(listOfAbunNo[i]+listOfAbunNo[j])
        j=j+1
    i = i+1

至

for i in range(len(listOfAbunNo)):
    for j in range(i, len(listOfAbunNo)):
        sums.append(listOfAbunNo[i]+listOfAbunNo[j])

所以你的整个代码现在看起来是这样的：

import time

def isAbundant(testNum):
    total = 1
    divisor = 2 
    while divisor < (testNum/2  + 1):
        if(testNum%divisor == 0):
            total = total + divisor
        divisor = divisor + 1   
    return total > testNum

start = time.time()
#create a list of abundant numbers
listOfAbunNo = []
for i in range(12, 28124):
    if isAbundant(i):
        listOfAbunNo.append(i)

# create list of sums of abundant numbers
sums = []
for i in range(len(listOfAbunNo)):
    for j in range(i, len(listOfAbunNo)):
        sums.append(listOfAbunNo[i]+listOfAbunNo[j])

#remove duplicates 
sums = list(set(sums))

#calc total
non_composites = sum([i for i in range(1, 28124) if i not in sums])
print(str(non_composites))
print('finished in ' + str(time.time()-start) + 's')

我添加了一个计时函数，代码在我的机器上大约在40秒内返回正确的结果。