尋找素數的<n

Question

我工作的項目歐拉，問題3. 的問題是：

「的13195的首要因素是5，7，13和29什麼是最大的 600851475143的素數？「

在回答這個問題時，我打算先找到所有素數< x（反過來）。爲什麼下面的代碼看起來不起作用，我不確定它是邏輯運算符還是不正確的運算符。

#A function to find prime numbers under n 
def find_prime(n): 
    for i in reversed(xrange(2, n)): 
     if (n % i) != 0: 
      print i 

find_prime(n) 

在測試中，我還建立了一個有趣的素數檢查器，所以我測試了一些。

def prime_checker(n): 
    if n > 2: 
    for i in range (2,n): 
     if (n % i) == 0: 
     print "%s is not a prime number" % (n) 
     break 
     else: 
     print "%s is a prime number" % (n) 

誰能幫我明白我在做什麼毛病find_prime（）函數之前我移動到，我將用它來解決問題的下一步是什麼？

Answer 1

在沒有找到任何除數的情況下，通過循環完成所有操作之前，您無法判斷數字是否爲素數。只要您找到一個不會將其分開的數字，您就可以報告一個數字是主數字，但它仍可以被更高的數字整除。你的代碼會說所有的奇數都是素數，因爲它們不是2的倍數。

此外，沒有必要一路去n在您的範圍內。數字的任何因素都不能大於數字的平方根。

def prime_checker(n): 
    if n > 2: 
    for i in range (2, int(n ** .5)+1): 
     if (n % i) == 0: 
     print "%s is not a prime number" % (n) 
     return false 
    print "%s is a prime number" % (n) 
    return true 

Answer 2

在你開始編碼之前，也許你應該閱讀一下你正在處理的內容。素材已被充分研究。首先，你不需要所有素數< x。其次，每當你找到一個除數時，你可以用這個數除以這個數，並且在你手上有一個小問題。最後，剩下的數字將成爲你正在尋找的東西。現在除了2，其他偶數都不是素數，所以xrange(3, n, 2)。再搜索一下，你會發現一個不需要宇宙完成時間的解決方案。