Euler 3 Python。把質數放入列表

我仍然很新的python，我試圖從600851475143所有的素數到列表中。但是，我不斷收到列表中的隨機數字，而不是素數。我不確定我會出錯的地方。感謝您的時間Euler 3 Python。把質數放入列表

import math 
factors_list = [] 
prime_factors = [] 

def number_factors(s): 
    s = int(math.sqrt(s)) 
    for num in range(2, s): 
     for i in range(2, num): 
      if (num % i) == 0: 
       factors_list.append(num) 
      else: 
       prime_factors.append(num) 

number_factors(600851475143) 

print factors_list 
print prime_factors

來源

2015-05-04 TheNuker

沒有與此算法的主要問題。建議：在循環中添加幾條打印語句，以查看算法產生的數字。不要試圖處理這個龐大的號碼，除非你確定你的代碼可以在你可以手動檢查的小號碼上正常工作。在相關說明中，您可能會發現使用鉛筆和紙張遵循您的算法很有幫助。 –

目前你追加到每一次if (num % i) == 0prime_factor。因此，例如，如果num=12（不是素數）和i=5，那麼您將會追加到prime_factor。

取而代之的是，如果它有沒有除數，那麼只應該追加，而不是隻有一個數字不能均勻分配。

雖然我會提前警告您，但這個問題不僅僅是關於計算素數，而是600851475143是一個非常大的數字。因此，您應該將當前的代碼作爲學習練習工作，但您需要重新考慮您的解決方案。

來源

2015-05-04 14:46:22 tom10

什麼是最好的方式來處理大數字？到目前爲止，我已經在我的 – TheNuker

類只有瞭解range和xrange一般情況下，我認爲這是對的歐拉問題的目標，以幫助解決。我在這裏幫了忙，因爲這是一個與問題核心無關的編程問題。至少在你尋求下一步的幫助之前，你自己嘗試一下。歐拉問題意味着很難。 – tom10

600851475143不_that_巨大的：它的最大素因子必須小於一百萬，實際上是7000下真，這將會是在有限的32位整數的語言問題，但它是因式分解在微風Python甚至用一個相當簡單的算法。 –

對於大數量，這將運行得相當緩慢。考慮算法嘗試尋找num = 1000000的主要因素的情況。嵌套的FOR循環將在下一個數字被考慮之前生成100萬次操作！

考慮使用Eratosthones篩來獲得所有素數達到某個整數。它不如某些其他Sieve效率高，但易於實施。花一些時間在實施之前閱讀篩選背後的理論 - 這將有助於您理解以後的問題。

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

來源

2015-05-04 14:55:47 manglano

我同意TheNuker需要在他們的算法上工作，但在這裏試用部門已經足夠 - 他們並不需要使用篩子。 –

下面是融通ň更好的算法。我會用文字來描述它，所以你可以自己編寫代碼。

1) Set f = 2. Variable f represents the current trial factor. 
2) If f * f > n, then n must be prime, so output n and stop. 
3) Divide n by f. If the remainder is 0, then f is a factor of n, 
    so output f and set n = n/f, then return to Step 2. 
4) Since the remainder in the prior step was not 0, set f = f + 1 
    and return to Step 2.

例如，對因子13195，首先設置˚F = 2;步驟2中的測試未得到滿足，步驟3中的剩餘部分爲1，因此在步驟4中設置f = 3並返回到步驟2.現在步驟2中的測試未得到滿足，步驟3中的剩餘部分爲1 ，因此在步驟4中設置f = 4並返回步驟2.現在步驟2中的測試未得到滿足，步驟3中的剩餘部分爲3，因此在步驟4中設置了f = 5並返回步驟2

現在步驟2中的測試未得到滿足，但步驟3中的剩餘部分爲0，因此5是13195的因子;輸出5，設置爲n = 2639，並返回步驟2.現在步驟2中的測試未得到滿足，步驟3中的剩餘部分爲4，因此在步驟4中設置了f = 6並返回步驟2。現在，在步驟2中的試驗是不滿足，則在步驟3中餘數爲5，因此在步驟4中設置˚F = 7，並返回到步驟2。

現在在步驟2中的試驗是不滿足，但步驟3中的餘數爲0，所以7是2639的因子（也是13195）;輸出7，設置爲n = 377，並返回步驟2.現在步驟2中的測試未得到滿足，步驟3中的剩餘部分爲6，因此在步驟4中設置了f = 8並返回步驟2。以這種方式繼續，直到f = 13。

現在，在步驟2中的試驗是不滿足，但是在步驟3中餘數爲0，所以圖13是377（以及2639和13195）的一個因素;輸出端13，設置Ñ = 29，並返回到步驟2中步驟2在這裏，測試是滿足，因爲13×13 = 169，其大於29，所以29是質數，它輸出和停止。最終分解爲5 * 7 * 13 * 29 = 13195.

的600851475143件作品中完全相同的方式的分解，不同之處在於它需要更長的時間。有更好的方法來整數。但是這個算法很簡單，對於PE3來說已經足夠了。

來源

2015-05-04 20:17:28 user448810

Euler 3 Python。把質數放入列表

回答

相關問題