項目歐拉＃23 Python

所以我在Project Euler＃23上工作，我需要一些有效的幫助。項目歐拉＃23 Python

好了，所以原來的問題是：

一個完美的編號是針對其適當除數的總和正好等於號。例如，28的適當因數的和將是1 + 2 + 4 + 7 + 14 = 28，這意味着28是一個完美的數字。

如果n的合適除數之和小於n，則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)

我做的研究公平分享，我確信有成千上萬的做這件事比我更好，但如果任何人有任何方程式或只是一個更好的方式來發現是正整數的方式兩個豐富的數字，我可以使用一些幫助的總和。

來源

2017-02-28 Jacob Green

出於好奇，爲什麼你覺得有必要（1）對因素進行排序或（2）將它們轉換爲浮點數？ – rici

@rici我在很久以前就做了分解代碼，但是我確實看到這是不必要的，我將它轉換爲float，因爲我經常會遇到一個錯誤，說我無法比較一個float和一個整數，所以我想象更容易把它全部變成浮動 –

據我所知，在Python中沒有允許比較浮點數和整數的情況。你無法將浮動與「十進制」進行比較，但這是相當不同的一堆魚。另外：使用'sum'函數。這比寫出循環要快得多。（測試增量和提前終止是一種錯誤的優化，測試至少使計算成本增加一倍，並且在總和中途你永遠不會發現豐富 - 你需要從最高到最低添加一個機會，甚至那麼大多數數字並不豐富。）... – rici

您可以將28124個布爾值的列表初始化爲False。然後遍歷豐富的數字，併爲每個數字找到所有等於或大於它的數字。對於每個總和x在列表True中設置第x個標誌。由於豐富的數字是按升序排列可以打破內部循環，當總和大於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!

來源

2017-02-28 03:16:49 niemmi

項目歐拉＃23 Python

回答

相關問題