フェルマーテスト

nが素数かを判定するプログラムです.

フェルマーの小定理に基いて出来ています.

フェルマーの小定理は

a,n が互いに素のとき

「nが素数　→　a^(n-1) modn = 1」

というものです.

対偶をとって

「a^(n-1) modn !=l 1 → nが素数でない(合成数)」

プログラムで書くとこんな感じです.

gist.github.com

ただし「a^(n-1) modn = 1 → nが素数」

とは保証されていないので素数以外で素数と判定されてしまいます.