Project Euler#23 Python非富足和

Question

我一直在研究Project Euler #23。在

任务如下：

Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis >even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

这是我的代码：

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。我花了一个小时查看代码，但找不到错误。我应该更改什么来更正错误？我的答案很接近。提前谢谢

另外，我是python新手。运行时间是25秒任何优化也将是有用的。在

Answer 1

我对上面提到的代码做了一些修改，在13秒内得到了正确的答案。我的CPU是英特尔酷睿i5。这是我的代码：

{from array import array


def find_abundant(number):
    import math
    sum_factor = 1
    value = math.ceil(math.sqrt(number))
    if number == 1:
        return False
    for i in range(2, value):
        if number % i == 0:
            sum_factor += (i+(number//i))
    if value**2 == number:
        sum_factor += value
    if sum_factor > number:
        return True
    else:
        return False


numbers = [0]*28123
abundant_numbers = array("i", [])
for abundant in range(1, 28124):
    if find_abundant(abundant):
        abundant_numbers.append(abundant)

for x in abundant_numbers:
    for y in abundant_numbers[0:abundant_numbers.index(x)+1]:
        z = x+y
        if z < 28124 and numbers[z-1] == 0:
            numbers[z-1] = z


_sum = 0
for vary in range(1, len(numbers)+1):
    if numbers[vary-1] == 0:
        _sum += vary
print(_sum)}

Answer 2

{cd1>函数不正确。它不计算平方数的根除数（例如，如果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。在