フェルマーテスト:
-
\(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 のプログラム:
Javascript のプログラム:
プログラミング へ戻る