紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

フェルマーテスト

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

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