项目Euler #23 Python

Question

因此，我正在研究Euler #23项目，我需要一些效率方面的帮助。

好的，原来的问题是：

完全数是指它的适当除数之和与其数完全相等的一个数。例如，28的适当除数之和为1+2+4+7+ 14 = 28，这意味着28是一个完美数。 如果一个数n的适当除数之和小于n，则称为亏，如果这个数大于n，则称它为富足数。 由于12是最小的富足数，1+2+3+4+6= 16，可以写成两个富足数之和的最小数是24。通过数学分析，可以证明所有大于28123的整数都可以写成两个丰富数的和。然而，这个上限不能通过分析进一步降低，即使已知不能表示为两个丰富数之和的最大数小于这个极限。 找出所有正整数的和，这些正整数不能写成两个丰富数的和。

我已经使大部分代码高效运行，但我遇到的一个问题是找到所有的数字是两个丰富的数字之和。

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。然后对这些丰富的数字进行迭代，并对每个数求出数等于或大于它的所有和。对于每一个和x，设置列表True中的xth标志。由于大量的数字是按升序排列的，所以当和大于28123时，可以打破内环。然后，在最后一步中，遍历列表，并将具有False值的所有indeces加在一起：

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!")

输出：

4179871
It took,  3.190303325653076  seconds!

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秒