素数判定

素数判定

なんとなく夜眠れないときに 101 あたりから順番に (97 までは覚えてる) 素数判定をしていたら 700 ぐらいまで行ったりしたときにいつのまにか使ってた判定方法を書いてみたくなったので書きます。

何でもいいけどいま 689 という数字が浮かんだので素数かどうか判定してみる。

3 で割れるかどうか調べる。689 → 8 → 割りきれない
7 で割れるかどうか調べる。689 → 640 → 8 * 8 * 10 → 割りきれない
11 で割れるかどうか調べる。689 → 6 - 8 + 9 → 1～10 のどれかっぽい → 割りきれない
13 で割れるかどうか調べる。689 → 650 → 65 → 5 * 13 → あっ割りきれた

そんな感じです。

ちょっと早すぎたので 691 でやってみると，2, 3, 5 は省略して

7 で割れるかどうか調べる。691 → 670 → 67 → 60 → 6 → 割り切れない
11 で割れるかどうか調べる。691 → 680 → 68 → 2 → 割り切れない
13 で割れるかどうか調べる。691 → 730 → 73 → 60 → 6 → 割り切れない
17 で割れるかどうか調べる。691 → 640 → 64 → 8 * 8 → 割り切れない
19 で割れるかどうか調べる。691 → 710 → 71 → 71 は素数 → 割り切れない
23 で割れるかどうか調べる。691 → 760 → 76 → 23*2 引くとなんか一桁の数の10倍 → 割り切れない
29 * 29 > 30 * 30 - 60 > 700 > 691 あっ素数だった

そんな感じです。

p で割れるか調べるときは適当に p の倍数を足したり引いたりして 10 の倍数にして末尾の 0 を落として，同じ手続きを繰り返して小さい数字を出します。十分に小さくなったら素因数分解するか，単純に p で割ってみるか，いかにも p の倍数じゃなさそうな大きさである (p = 23 で，30 台とか 50 台の数字が出てきたときとか) ことを根拠に判定します。