python素數檢查的難點

我一直在試着讓這段代碼能夠返回一個輸入數字作爲2到49之間的素數，但它所做的只是返回大部分數字作爲素數，即使它們不是。。對於演習中，我得到了這3，5，7個總理，無論如何，所以就忽略這個問題有點...python素數檢查的難點

def prime(a): 
if a < 2: return False 
if a % 2 == 0: return False 
if a == 3 or a == 5 or a == 7: return True 
for n in range(3,int(a ** 0.5) + 1): 
    if a % n == 0: return False 
    if a % n != 0: return True 

a = input("Enter a number between 1 and 49: ") 

if prime(a) is False: 
    print a, " is not a prime number" 

if prime(a) is True: 
    print a, " is a prime number"

來源

2012-10-17 Oli

這不是算法你正在使用，但它是有趣的和相關的：對素數有一個概率測試，它使用費馬小定理（見https://en.wikipedia.org/wiki/Fermat_primality_test）。你必須得到1729年才能找到一個通過測試相對於2,3和5的數字，但不是素數。（而且只有四個這樣的<10000）。 – dubiousjim

for n in range(3,int(a ** 0.5) + 1): 
    if a % n == 0: return False 
    if a % n != 0: return True # This if condition is not needed

你並不需要一個第二，如果條件。否則當數字不能被當前值n整除時，它將立即返回。但你不想那樣。如果當前的n不能劃分你的號碼，你需要檢查下一個值。

所以，只要刪除，如果，並添加return True循環結束以後。

所以，您prime()方法應該是這樣的： -

def prime(a): 
    if a < 2: return False 
    if a % 2 == 0: return False 
    if a == 3 or a == 5 or a == 7: return True 
    for n in range(3,int(a ** 0.5) + 1): 
     if a % n == 0: return False 

    return True

來源

2012-10-17 22:14:26

python素數檢查的難點

回答

相關問題