使用費馬小定理計算素數時的值4

Question

我寫了一個現在並不重要的程序，但它是在這個費馬定理上的。現在的問題是產量不像預期的那樣。我知道這個問題不是太好或不符合標準，但我不能解決這個錯誤，即在輸出中出現了4個錯誤，而這個錯誤不可能存在。我無法調試它。

定理：

for x in range(1,100): 
m=5**(x-1) 
if m%x>1:  
    pass 
else: 
    print"prime",x 

輸出是這樣的：

Answer 1

一個完美的解釋這裏找到：https://stackoverflow.com/a/29596459/5110035

基本上這種方法不是很準確。 我在你的代碼中找到了一個模式。如果選擇a 5，則打印非素數a-1。這就是爲什麼4出現。將其更改爲7，你會得到6，還包括其他錯誤，拿出比如25

費馬小定理可以很容易地用Python寫的是這樣的：

def CheckIfProbablyPrime(x): return pow(2, x-1, x) == 1

的唯一原因，我認爲四個出現是因爲你的算法有點不正確。 Eratosthenes的篩子，一旦它發現一個非素數，然後擺脫它的倍數，例如4是2的倍數，但2是質數，因爲4不是。它檢查的數量更少，速度更快。研究一下。