IsPrime函數錯誤？

我寫了這個函數來檢查一個數是否爲素數。它似乎工作正常，但是當我在另一個函數中使用它時，它似乎不工作。IsPrime函數錯誤？

這裏是我的IsPrime功能：

def is_prime(n): 
    boolean = False 
    if n == 2 or n == 3: 
      return True 
    for x in range(3, int(n**0.5)+1, 2): 
     if n % x == 0: 
      return False 
    return True

了以下功能計算200萬下的所有質數的和：

def problem10(prime, result): 
    if prime > 2000000: 
     return 
    if is_prime(prime): 
     print 'prime is ', prime 
     result = result + prime 
     problem10(prime + 1, result) 
    return result

我能不明白的地方我已經錯了。

評論將不勝感激。

來源

2012-09-19 Hummus

當數字不是素數時會發生什麼？ – ovgolovin

請澄清你的意思是「似乎不起作用」。 – jpm

另外，你爲什麼遞歸調用problem10與下一個有問題的數字？ for循環必須更加高效，並且不會導致堆棧溢出 – Serge

is_prime不檢查偶數。例如，如果你通過它4，它會看到它既不是2也不是3，然後進入循環，它會執行一次，檢查它是否可以被3整除（不是它）。退出循環，當我們知道4實際上不是素數時，它將返回True。

來源

2012-09-19 20:30:41 jpm

+1來解釋實際出錯 – georg

@ thg435這不是OP代碼中唯一錯誤的事情。在「problem10」代碼中也有一個明顯的錯誤。 – Bakuriu

如果你被檢查範圍內使

for x in range(2, sqrt(n)+1): 
    if n % x == 0: 
     return False

沒有根將永遠比平方根大。

來源

2012-09-19 20:31:59 Evo510

這是不正確的：你_do_必須檢查平方根。如果你在該範圍內使用'n **。5'的地板作爲「停止」，它將不會被包含在內，因此你會錯過素數的平方。如果你的意思是這樣，那麼從示例代碼中就不清楚了。 – Bakuriu

'n ** 0.5'確實如此。但是，import math.sqrt'更快。 – Droogans

@Bakuriu這是我的錯誤遺忘範圍（2，sqrt（n））不包括sqrt本身。 – Evo510

您在problem10函數的流程中有錯誤。這歸結爲事實上你並沒有實際使用遞歸函數的結果值。你希望你的代碼看起來像這樣（假設你想保持你的遞歸，你可能要考慮一個循環，而不是）：

def problem10(prime): 
    """ calculates the sum of primes from this prime until 2000000 (2 * 10**6) """ 
    if prime >= 2000000: 
     return 0 
    elif is_prime(prime): 
     return prime + problem10(prime + 1) 
    else: 
     return problem10(prime + 1)

注意，此功能的方法有幾個關鍵點需要考慮：

如果prime> = 2000000，那麼這個函數表示空的和。因此返回0.
如果is_prime（prime），那麼這個函數應該加上素數
否則，總和與下一個數字的素數總和相同（因爲我們不得不排除低數字因爲它不是素數）。
與您最初的嘗試相比：注意如何在return語句中使用表達式可以大大簡化函數的邏輯（流程）。它的確更具可讀性。此外，請注意您的原始功能永遠無法工作，因爲：

a。您的功能不會更新運行總數（結果）

b。即使是這樣，最終你最終會添加None，因爲你的原始函數在prime> = 2000000的情況下什麼也沒有返回。

來源

2012-09-19 20:42:37 user268396

我運行了你的代碼，但它仍然給我一個最大的遞歸深度錯誤。 – Hummus

這並不奇怪，你的上限是2000000，又叫200萬，你需要每個數字遞歸一次。所以你需要大約200萬次遞歸，每次遞歸都需要一些堆棧。 Python對遞歸有一個內置的限制，以保護您免受堆棧空間不足的後果。這就是爲什麼（除其他之外），你想要考慮一個循環，因爲它沒有出現這些問題和限制。 – user268396

更快的素數表是這樣的：

import numpy as np 

def primesfrom2to(n): 
    """ Returns a array of primes, p < n """ 
    assert n>=2 
    sieve = np.ones(n/2, dtype=np.bool) 
    for i in xrange(3,int(n**0.5)+1,2): 
     if sieve[i/2]: 
      sieve[i*i/2::i] = False 
    return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]

隨後的只是總和：

print sum(primesfrom2to(2000000))

如果你想使用你的函數，這裏是一個建議重寫：

def is_prime(n): 
    if n in (2,3): 
     return True 
    if not n%2: 
     return False   
    if any(n%x == 0 for x in xrange(3, int(n**0.5)+1, 2)):  
     return False 
    return True

來源

2012-09-19 21:45:19

這是一個您is_prime功能，它使用試用除以2個，奇數3至ñ平方根，以確定是否n是素數或複合的正確版本：

def is_prime(n): 
    if n % 2 == 0: 
     return n == 2 
    d = 3 
    while d * d <= n: 
     if n % d == 0: 
      return False 
     d += 2 
    return True

一個更好的辦法來解決問題就是使用Eratosthenes的Sieve來確定所有小於2000000的素數，然後求和它們。這裏的埃拉托色尼的簡單篩：

def sieve(n): 
    b, p, ps = [True] * (n+1), 2, [] 
    for p in xrange(2, n+1); 
     if b[p]: 
      ps.append(p) 
      for i in xrange(p+p, n+1, p): 
       b[i] = False 
    return ps

有更好的（快）的方式都確定一個數是質複合材料和產生的所有質數的列表，但是這些都足以讓你的任務。

來源

2012-09-19 22:15:20 user448810

def isPrime(num,div=2): 
if(num==div): 
    return True 
elif(num % div == 0): 
    return False 
else: 
    return isPrime(num,div+1)

來源

2014-02-20 09:58:42 namco

IsPrime函數錯誤？

回答

相關問題