Euler 23 Python项目

Question

所以我在做Euler 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
import time
def factors(n):
    fact=[1,n]
    check=2
    rootn=math.sqrt(n)
    while check<rootn:
        if n%check==0:
                fact.append(check)
                fact.append(n/check)
        check+=1
    if rootn==check:
        fact.append(check)
    fact.sort()
    return fact

abundantNumbers = []
timeStart = time.time()
for i in range(12, 28124):
    factorTemp = factors(i)
    totalTemp = 0
    factorTemp.remove(i)
    for j in range(len(factorTemp)):
        factorTemp[j] = float(factorTemp[j])
    for j in range(len(factorTemp)):
        totalTemp+=factorTemp[j]
        if totalTemp> i:
            abundantNumbers.append(i)
            break
nums = []
doubleAbu = []
for i in range(24, 28124):
    nums.append(i)

for j in abundantNumbers:
    if j*2 < 28123 and j*2 not in doubleAbu:
        doubleAbu.append(j*2)

for i in abundantNumbers:
    repeat=True
    for j in abundantNumbers[abundantNumbers.index(i):]:
        if i + j not in doubleAbu and i + j <28123:
            doubleAbu.append(i+j)
        elif i + j > 28123:
            break
            repeat = False
    if not repeat:
        break
total = 0
for i in range(len(doubleAbu)):
    nums.remove(doubleAbu[i])
for i in range(len(nums)):
    total += nums[i]


print("It took, ", str(time.time()-timeStart), " seconds!")
#print((abundantNumbers))
print(doubleAbu)
print(total)

我做了相当多的研究，我确信有成千上万的方法比我做得更好，但是如果有人有任何方程或者只是找到一个更好的方法来找到正整数，那就是两个丰富的数字之和，我可以帮上一些忙。在

Answer 1

您可以将28124个布尔值初始化为False。然后在富足数上迭代，对于每一个数，找出所有数等于或大于它的和。对于每个sum x，在列表True中设置第xth标志。由于富足数是按升序排列的，因此当总和大于28123时，您可以打破内部循环。然后在最后一步迭代列表，并将具有False值的所有索引相加：

import math
import time
def factors(n):
    fact=[1,n]
    check=2
    rootn=math.sqrt(n)
    while check<rootn:
        if n%check==0:
                fact.append(check)
                fact.append(n//check)
        check+=1
    if rootn==check:
        fact.append(check)
    fact.sort()
    return fact

abundantNumbers = []
timeStart = time.time()
for i in range(12, 28124):
    factorTemp = factors(i)
    totalTemp = 0
    factorTemp.remove(i)
    for j in range(len(factorTemp)):
        factorTemp[j] = float(factorTemp[j])
    for j in range(len(factorTemp)):
        totalTemp+=factorTemp[j]
        if totalTemp> i:
            abundantNumbers.append(i)
            break

MAX = 28123
result = [False] * (MAX + 1)

for i in range(len(abundantNumbers)):
    for j in range(i, len(abundantNumbers)):
        s = abundantNumbers[i] + abundantNumbers[j]
        if s > MAX:
            break
        result[s] = True

print(sum(i for i, x in enumerate(result) if not x))
print("It took, ", str(time.time()-timeStart), " seconds!")

输出：

^{pr2}$

Answer 2

有一个更快更短的版本，尽管我很确定它仍然可以改进。在

import time
from math import ceil

# Sum of Proper Divisors of
def sopd(n):
    if n == 1: return 0
    s = 1
    sqrt = ceil(n ** 0.5)
    for b in range(2, sqrt):
        if n % b == 0:
            s += (b + n // b)
    return s + (sqrt if sqrt ** 2 == n else 0)

if __name__ == '__main__':
    start_time = time.time()

    abundant = set()
    s = 0
    for i in range(1,28124):
        if not any(i-a in abundant for a in abundant):
            s += i
        if sopd(i) > i:
            abundant.add(i)
    print(s)
    print(" - {} seconds  -".format(time.time() - start_time))

在我的电脑上大约需要1.2秒