フェルマーテスト：

\(n\) に 素数かどうか判定したい自然数を入力する。
100 回繰り返す：
　　\(m\) を 2 から \(n-1\) までの自然数からランダムに選ぶ
　　\(m\) が \(n\) と互いに素でなければ、\(n\) は素数ではない。
　　\(m^{\ n-1}\) を \(n\) で割った余りが 1 でなければ、\(n\) は素数ではない。
ここまでして \(n\) は素数ではないと判定されなかった場合には、\(n\) は素数であると判定する。


　　　　　



　200 未満の素数：
　　　2　3　4　5　7　11　13　17　19　23　29　31　37　41　43　47　53　59　61　67
　　　71　73　79　83　89　97　101　103　107　109　113　127　131　137　139　149
　　　151　157　163　167　173　179　181　191　193　197　199　

　なんと、17 以上の素数はすべてミスジャッジされてしまいます。これは JavaScript が正確に扱える整数が−9,007,199,254,740,991 〜 9,007,199,254,740,991 までの範囲だからです。そこで、多桁整数を正確に扱うことのできる Pyhton に移植してみます。

Pyhton のプログラム：
import math import random def prime(n): if n == 1: return False if n == 2: return True for i in range(100): a = random.randint(2,n-1) if gcd(n,a) != 1: return False if pow(a,int(n-1))%n != 1: return False return True def gcd(a,b): while b > 0: a, b = b, a%b return a num = int(input("素数判定を受ける自然数")) if prime(num): print (f"{num} は 素数です。") else: print (f"{num} は 素数ではありません。")
　Pyhton のプログラムでは、ほぼ 100% 正解です。

Javascript のプログラム：