紙媒体で知識や経験を管理すると無くなりがちなのでブログで管理することにしました.
      殆どの記事は自分自身のためだけに書いているため,他人に見せる前提の内容, 文章ではありません.
      また, ブログのコメント欄を解放していたらbotからの迷惑行為を受けたため現在コメント欄は解放しておりません.

フェルマーテスト

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が素数

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