项目Euler #23 - Python的非富足和

Question

我一直在研究Project Euler #23。

这是一项任务：

问题23 完全数是指它的适当除数之和与其数完全相等的一个数。例如，28的适当除数之和为1+2+4+7+ 14 = 28，这意味着28是一个完美数。 如果一个数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.I花了一个小时查看我的代码，但是我找不到错误。我应该修改什么来纠正错误？我的回答已经接近了。提前感谢

PS。我对蟒蛇很陌生。运行时是25s，任何优化都是有用的。

Answer 1

您的getDivisors函数不正确。它不计算平方值的根除数(例如，如果是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。

Answer 2

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

from array import array
import math


def find_abundant(number):
    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 3

此代码在我的计算机上运行6秒：

from math import sqrt
import itertools
import functools
import operator
#simplicity test
def fuc(a):
    d = 1
    z = 0
    while d<= sqrt(a):
        d = d + 1
        if a == 2:
            z = a
        elif (a%d) == 0:
            z = False
            break

        else:
            z = a
    return z
#prime number divisors
def func(value):
    v = []
    d = 1
    value1= value# for optimization
    while d <= sqrt(value1):
        d+=1
        if fuc(d)!= False and value1 % d == 0:
            v.append(d)
            value1 = value1/d
            d = 1
    if value1 != value and value1 != 1:
        v.append(value1)
    return v
# all number divisors without 1 and source number
def calculate_devisors(n):
    prime_multiples_list = func(n)
    unique_combinations = set()
    for i in range(1, len(prime_multiples_list)):
        unique_combinations.update(set(itertools.combinations(prime_multiples_list,i)))
        combinations_product = list(functools.reduce(operator.mul,i) for i in unique_combinations)
        combinations_product.sort()
    try:
        return combinations_product
    except:
        return []

abundentNums = []

for n in range(1,28123):
    if sum(calculate_devisors(n))+1>n:
        abundentNums.append(n)

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
ans = 0
for i in range(1,len(sums)):
    if sums[i]==0:
        ans+=i
print(ans)