Fermat's Little Theoremを使用して素数を計算するときの値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が来るのです。私が思う唯一の理由

に

def CheckIfProbablyPrime(x): return pow(2, x-1, x) == 1：7に変更し、あなたが6を得る。しかし、他のエラーは、25

として出てくるフェルマーの小定理は簡単にこのようにPythonで記述することができあなたのアルゴリズムがちょっと間違っているために4つが現れます。エラトステネスのふるい、一度それが非プライムを見つけると、4が2の倍数であるが、4がそうではないので2が素数であるなどの倍数を取り除く。それは少ない数とはるかに速くチェックします。それを見てください。