歐拉項目＃10

我對算法很陌生，剛開始編碼週迴來。請幫我出這一個：歐拉項目＃10

素數之和小於10爲2 + 3 + 5 + 7 = 17

見以下兩個萬支全質數的總和。

我嘗試通常的蠻力方法，該方法ofcourse吸入。我嘗試閱讀Sieve算法。並實現了這一點，是的，它只是爲奇數運行：

i=[x for x in range(3,2000001,2)] 
print(len(i)) 
j=0 
sum=2 
while(max(i)!=j): 
    m=0 
    while(m<(2000000-(i[j]**2)/(2*i[j]))): 
     a=(i[j]**2)+2*m*i[j] 
     if a in i: 
      i.remove(a) 
     m+=1 
    j+=1 
for s in range(1,len(i)+1): 
    sum+=i[s] 
print(sum)

程序仍然需要像5個多小時。我在3小時內停止了它。我哪裏錯了？

來源

2014-04-25 Ashtrix

蠻力通常不夠好項目歐拉問題。你必須找到一種加速找到正確答案的算法。看看「算法分析」或AofA領域。某些問題的一些算法非常高效，並且可以使您的加速達到百萬倍。您還應該考慮記憶和動態編程（DP）。 –

看來你正在努力學習，所以我不會給你完整的解決方案，只是路徑。

不要亂搞清單，把元素放入和放出，檢查它們是否在，等等。這是低效率的祕訣。相反，保留已知素數列表。
寫評論。我一直盯着你的代碼幾分鐘，我不知道它的作用。
適用時使用math函數。 math.sqrt比**0.5快（約增加30％）。
此塊： for s in range(1,len(i)+1): sum+=i[s] 傷害。您可以通過以下方式獲得列表總和：打字sum(i)
[x for x in range(3,2000001,2)]與range(3,2000001,2)（在Python2中）或list(range(3,2000001,2))（在Python3中）完全相同。
不要使用變量名稱爲i，a，m。目前尚不清楚它們是什麼。

你怎麼知道一個數字是否是總數？對於它下面的所有素數，檢查他們是否將你的數字分開。如果沒有，請保存。事實上，您只能檢查那些比數字的平方根小的素數。

如果你想交換內存的速度，你可以使用@vamosrafa的功能，並做sum(prime(2e6))。（在Python2中更改爲range爲xrange）。你只需要記憶同時保存幾個數字，但是會做很多不必要的分割（如果它不能被3或5整除，它將不能被15整除）。

來源

2014-04-25 10:38:29 Davidmh

這些是一些非常方便的提示！萬分感謝！ – Ashtrix

@Davidmh：是的，收益率方法會消耗內存，這就是爲什麼，這不是一個好方法，因爲我一直在用篩選方法掙扎，它需要5個小時的時間。 – vamosrafa

我在同也卡住了，花了兩個晚上出局，解決這個問題。

於是，我拿起Mark Pilgrim的DIVE INTO PYTHON，並有一個約發生器功能章節，我應用該技術來解決這個問題。下面是這將解決這個問題發生器功能：

def prime(max): 

    for n in range(2,max): 

     for x in range(2,int(n**0.5) + 1): 

      if n%x == 0: 


       break 
     else: 

      yield n

現在，寫另一個函數總和，這將調用該方法，無論是在外殼或在這個程序本身，我曾呼籲在外殼的總和，但是這將解決你的問題。

祝你好運！ :)

來源

2014-04-25 10:16:52 vamosrafa

雖然通常用於測試素數的好方法，但這不能解決用戶的問題（它們的實現有什麼問題），也不會使用所提到的篩選方法。 – jonrsharpe

是的，我已經發布了一個優化方法，採用篩選方法，對我來說，處理時間相當於5小時。 – vamosrafa

哇，真的？！你在運行什麼？在我的例子中相對天真的篩子花費了大約2秒。你可能想把你的代碼放到http://codereview.stackexchange.com並獲得一些幫助來加速它。 – jonrsharpe

篩是一種很好的方法，但是你的實現很混亂，顯然不能正常工作。考慮這個非常簡單的（未優化）的實現：

def prime_sieve(max_): 
    """Create a list containing all prime numbers equal to or less than max_.""" 
    primes = list(range(max_+1)) # all numbers 0 to max_ 
    primes[1] = 0 # 1 is not prime 
    for number in primes: # iterate through all numbers 
     if number: # if not 0 (i.e. prime) 
      for multiple in range(2, (max_ // number) + 1): 
       primes[number * multiple] = 0 # set multiples to zero 
    return primes

這可能更有效率，但是在大約兩秒鐘max_ == 2000000運行我的機器上。

使用for循環通常比用於迭代容器（如列表）的while循環更好。還要注意，我在列表中留下了非素數，但將它們設置爲零 - 否則索引（代碼中的i[j]）將會中斷。

對於測試例如：

>>> prime_sieve(10) 
[0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0] 
>>> list(filter(None, prime_sieve(10))) 
[2, 3, 5, 7] 
>>> sum(prime_sieve(10)) 
17

來源

2014-04-25 10:43:14 jonrsharpe

一個改進能夠基於@jonrsharpe提供的代碼進行 - 取代for multiple in range(2, (max_//number)+1):與for multiple in range(number, (max_//number)+1):

def prime_sieve2(max_): 
     primes = list(range(max_+1)) 
     primes[1] = 0 
     for number in primes: 
       if number: 
         # starting from number rather than 2 
         for multiple in range(number, (max_//number)+1): 
           primes[number * multiple] = 0 
     return primes

前的評估步驟（你可以看到評估從2到數字^ 2可以跳過）：

check 2, 4, 6, 8, 10, 12, 14,... 
check 3, 6, 9, 12, 15, 18, 21,... (6 is already checked by '2') 
check 5, 10, 15, 20, 25, 30, 35,... (10, 15, 20 are already checked by '2' and '3') 
check 7, 14, 21, 28, 35, 42, 49, 56,... (again, 14, 21, 28, 35, 42 are redundant checked)

個

增強後的評估步驟：

check 4, 6, 8, 10, 12, 14,... 
check 9, 12, 15, 18, 21,... 
check 25, 30, 35, ... 
check 49, 56, ...

來源

2015-01-22 13:10:49

回答

相關問題