素数判定をしてみよう！！

こんにちは、youjo_tape でございます
本記事は、アドベントカレンダー2017 において、2017/12/03 分を担当しています。

はじめに

突然ですが、この日付にちなんで 素数判定 の問題を出します：

ㅤㅤ
　この記事が投稿された年月日　 $20171203$ 　は、素数でしょうか？
　（計算機や、メモなどの外部記憶装置を用いてはいけません）
ㅤㅤ

本サークル、デジタル創作同好会traP が所在する 大岡山素数大学 の学生は、この程度の素数判定はぱぱっとやってしまうのですが、一般的には、ある数が素数かどうか判定するのは、簡単な問題ではありません。
そんな素数判定ですが、これができるようになると、

街で見かけた数字に対して素数判定を実行することで、暇をつぶすことができる
素数判定が必要なゲーム^[1]で強くなれる
RSA 暗号を解ける
素数と友達になれる

などなど、たくさんの恩恵を受けることができます。
そこで、本記事では、素数判定を暗算でも素早く行えるようになるテクニックをあなたに伝授します！

※ 本文の読みやすさ・わかりやすさを重視して、本題からそれた補足的な話や、ちょっと難しめの理論的な話は、注釈に分離しておきました

素数判定をしよう

素数判定の基本

まずは小手調べとして、 $1001$ の素数判定をしてみましょう。
そもそも素数とは、「1とその数以外の正の約数を持たない自然数」を指すのでした^[2]。
このことから、 $1001$ が素数であるかどうかを調べるには、

2, 3, 4, 5, \dots, 997, 998, 999, 1000

で割り算をしてみて、どれでも割り切れないことを確かめればよいといえます。（裏を返せば、どれか1つで割り切れてしまえば、1001 は素数ではないことがわかります）
しかしながら、この方法では、最悪 999 回も割り算をしないと判定できません。とても面倒ですね。

実は、ある数 $n$ が素数かどうか判定するには、「 $n$ 以下の素数で割り切れるかどうか」さえ確かめればよい、という事実があります^[3]。
これを踏まえると、 $1001$ が素数であるかどうかを調べるには、 $3 1^{2} < 1001 < 3 2^{2}$ なので、 $1001$ 以下の素数：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

で割りきれるかどうかをチェックするだけで十分なのです。最大でも、たった 11 回の割り算で済みますね。
あとは、実際に割り算をやってみると、意外と早いところで $1001$ を割り切る素数が見つかって、

1001 = 7 \times 11 \times 13

であることがわかります。^[4]
実は、この結果を知っていると、素数判定が少し簡単に行えるようになります。後で登場するので、記憶の片隅に置いておいてください

素数判定のテクニック

次に、少し難度を上げて、 $3187$ の素数判定をしてみるとともに、素数判定のテクニックを紹介していきます。
まず、 $5 6^{2} < 3187 < 5 7^{2}$ ^[5] であることから、 $2, 3, 5, 7, \dots, 53$ という 16 個の素数についてチェックすればいいとわかります。
順に見ていきましょう。

$2, 5$
　もとの数の1桁目を見れば、一目瞭然ですね

$3$
　有名な倍数判定法「ある数が3の倍数である $\Leftrightarrow$ 各桁の数の和が3の倍数である」^[6] で一発です

$7$

3187 \equiv 318 \equiv (318 \div 2) = 159 \equiv (159 - 140) = 19 \neq \equiv 0 (mod 7)

突然謎の数式が出てきましたが、ざっくり言えばこの式は、「 $n$ で割り切れるかどうか」が変わらないように、もとの数を小さくしていく流れを表しています。（本記事の $\equiv$ は、一般に使われている合同関係とはちょっと違うので注意してください^[7]）
「 $n$ で割り切れるかどうか」を変えない変形とは、具体的には、

$n$ の倍数を足す、引く
$n$ と互いに素な（共通の素因数を持たない）数で割る、掛ける

などです。上記の変形を行って、明らかに $n$ で割り切れない数に変形できれば、もとの数も $n$ では割れないということが言えるのです。また、変形により $n$ の倍数になったなら、もとの数は $n$ で割り切れる、すなわち素数ではないと結論できます。

先の数式を「実際に頭の中で行う思考」に翻訳すると、

$3187$ を、 $7$ で割り切れるかどうかが変わらないように小さくしていこう
1 桁目の $7$ はもちろん $7$ で割り切れるから、残りの $318$ が $7$ で割り切れるか調べればいいわけだ
$318$ を $2$ で割って $159$ 、さらに $7 \times 20 = 140$ を減じて $19$ 、これは $7$ では割り切れない
つまり、もとの数 $3187$ も $7$ では割り切れないな！

といった感じになります。 $7$ のような小さい素数だと、この方式によるありがたみはあまり感じられませんが、割る数が大きくなって割り算をするのが難しくなってくると、とても重宝します。
「数を小さくするやりかた」は色々ありますが、どのように計算するのが楽かは、割る数・割られる数によって異なるうえ、けっこう個人差もあるようなので、やりやすい方法を試行錯誤してみてください。

ㅤ
ㅤ
ところで、今は $7$ のチェックを行ったのですが、実は $7, 11, 13$ はまとめてチェックすることができるのです！

$7, 11, 13$

3187 \equiv (3187 - 1001 \times 3) = 184 \equiv 92 (mod 7 \times 11 \times 13)

さきほど出てきた $1001 = 7 \times 11 \times 13$ を使いました。この他にも、例えば：

$969 = 3 \times 17 \times 19 = 1000 - 31$ ^[8]
$2001 = 3 \times 23 \times 29$

などが、素数判定の序盤によく使う数として挙げられます。これを知っていれば、判定のスピードがかなり上がるはずです！

$17, 19$

3187 \equiv (3187 - (1000 - 31) \times 3) = 280 \equiv 28 (mod 17 \times 19)

$23$
先ほど紹介した $2001$ を使うルートで $23, 29$ を同時にチェックしてもよいのですが、今回のケースだとそのルートは少し難しいので、ここは素直に個別にチェックします^[9]

3187 \equiv (3187 + 23) = 3210 \equiv 107 \neq \equiv 0 (mod 23)

$29$
$287 - 290$ といった引き算は、計算しやすいようにひっくり返してしまって問題ありません

3187 \equiv (3187 - 2900) = 287 \equiv (290 - 287) = 3 \neq \equiv 0 (mod 29)

$31$

3187 \equiv (3187 - 3100) = 87 \neq \equiv 0 (mod 31)

$37$
$3 \times 37 = 111$ であることがたまに役に立ちます（今回は使っていない）

3187 \equiv (3187 - 37) = 3150 \equiv 63 \neq \equiv 0 (mod 37)

$41$
基本的な方針としては、最下位を消すように加減算をしていくのがおススメです

3187 \equiv (3187 + 41 \times 3) \equiv (331 - 41) \equiv 29 \neq \equiv 0 (mod 41)

$43$

3187 \equiv (3187 + 43) \equiv (323 - 43) \equiv 28 \neq \equiv 0 (mod 43)

$47$

3187 \equiv (3187 - 47) \equiv 314 \equiv (157 - 47) \equiv 11 \neq \equiv 0 (mod 47)

$53$

3187 \equiv (3187 + 53) \equiv 324 = 1 8^{2} \neq \equiv 0 (mod 53)

以上で、 $2, 3, 5, 7, \dots, 53$ におけるチェックが全て通ったので、 $3187$ は素数です！

その他のテクニック

チェックを流用する

少し高度ですが、それまでの素数チェックで行った計算が流用できる場合があります。

例

先ほど行った $3187$ の $7, 11, 13$ チェックにおいて、
$3187 \equiv (3187 - 1001 \times 3) = 184 \equiv 92 (mod 7 \times 11 \times 13)$
と計算しましたが、このことから、
$3187 = 23 で割り切れない 1001 \times 3 + 23 で割り切れる 2 \times (2^{2} \times 23)$
に気づくことができれば、 $3187$ は $23$ では割り切れないとわかり、 $23$ のチェックは不要になります！

素数を覚える

ある程度小さな素数を覚えておけば、素数判定のスピードはさらに上がります。
今回の例でいえば、 $41$ チェックにおける $331$ や、 $47$ チェックにおける $157$ が素数であることを知っていれば、その時点で割り切れないことがわかるためです。^[10]

（そもそも、判定したい数がある程度大きい場合は、試し割りする素数も大きいものになってくるのですが…。たとえば、冒頭の問題で出てきた $20171203$ は素数ではありません（実際、 $20171203 = 13 \times 157 \times 9883$ と素因数分解されます。 $1001$ チェックの段階で引っかかるので、素数判定をするだけなら簡単ですね）。しかし、これが仮に素数であったとしたら、 $4483$ までの素数 609 個をチェックしないといけません。流石に人力では現実的じゃないですね^[11]）

因数分解公式を使う

$10 n \pm 1$ の形をした素数のチェックでは、 $100 n^{2} - 1 = (10 n + 1) (10 n - 1)$ を考えると計算しやすいときがあります。

例

$5183$ の $71$ チェックにおいて、 $4900 - 1 = 69 \times 71$ を用いると、
$5183 \equiv (5183 - (4900 - 1)) = 284 \equiv 0 (mod 71)$
と判定できます。

これと似たテクニックとして、 $10 n + 3, 7$ の形をした素数のチェックで $100 n (n + 1) + 21 = (10 n + 3) (10 n + 7)$ が使えるかもしれないですが、筆者は使ったことがないです

まとめ

ある数 $n$ の素数判定は、以下のステップで行えます：

$n$ 以下で最大の素数 $p_{max}$ を求める（ $p^{2} \leq n$ をみたす素数 $p$ のうち最大のものを探せばよい）。
素数 $2, 3, 5, \dots, p_{max}$ に対して、以下を行う：
- $n$ をうまく変形していって、 $n$ が $p$ で割り切れるか判定する。
  割り切れたら、 $n$ は素数ではない。
  - このとき、 $1001 = 7 \times 11 \times 13$ などを知っていると、判定スピードが速くなる！
すべてチェックが通ったら、 $n$ は素数である。

この記事をここまで読んでくださったあなたは、もはや何も恐れることはなく素数判定ができるはずです。素数判定ができなくて困っている人を見かけたら、是非ずばっとジャッジを下してあげてくださいね！

明日の記事

明日の記事は、 DP さん,　yu_ さん,　hukuda222 さんの担当です。お楽しみにどうぞ～

素数大富豪、素数山手線ゲームなど ↩︎
より一般には、整域（ある程度計算がうまくいく構造） $R$ の元 $p$ について、「 $0$ ではなく、逆元を持たず、 $a, b \in R$ に対して『 $p$ が $a b$ を割り切るならば $a$ または $b$ を割り切る』」とき、 $p$ は素元である、というようです。
（「逆元を持たない」という条件は、整数や複素整数などでは「1(とそれに相当するもの)は素数ではない」ことに相当し、実数や有理数などでは「素元が存在しない」ということを意味します。うまくまとまってますね）
ちなみに、ここでは詳しく紹介しませんが、複素整数においては $2 = (1 + i) (1 - i)$ が素数でなかったりして面白いです。今回の記事の内容として、このような「素数とは何か」「素数にはどんなものがあるのか」など、理論的な話をするか、今回のような実践的な話をするか、あるいは両方詰め込むか、かなり迷ったのですが、本記事の形に落ち着きました。 ↩︎
$n$ が、ある素数ではない整数 $a (1 < a < n)$ で割り切れるとします。
すると、 $a$ は素数ではないことから、 $a$ を割り切る素因数 $p (1 < p < a)$ が存在して、 $n$ は $p$ で割り切れます。つまり、「 $n$ が $a$ で割り切れる $\Rightarrow$ $n$ が $p$ で割り切れる」が成り立ちます。
これは、 $n$ が素数ではない数 $a (< n)$ で割り切れるなら、 $n$ が素数 $p (< n)$ でも割り切れることを意味しているので、 $n$ が素数であるか調べるためには、 $n$ 未満の素数で割り切れるかどうか だけ確認すればよいとわかります。
ㅤㅤ
次に、 $n$ が、ある整数 $a (n < a < n)$ で割り切れるとします。
このとき、 $\frac{n}{a}$ は整数となるので、この整数を $b = \frac{n}{a}$ とおくと、 $a$ がとりうる値の範囲から、 $1 < b < n$ が従います。また、 $\frac{n}{b} = a$ なので、 $n$ は $b$ で割り切れることがわかります。これにより、「 $n$ が $a$ で割り切れる $\Rightarrow$ $n$ が $b$ で割り切れる」が成り立ちます。
これは、 $n$ が $a (> n)$ で割り切れるなら、 $n$ が $b (< n)$ でも割り切れることを意味しているので、先の議論と合わせると、 $n$ が素数であるか調べるためには、 $n$ 以下の素数で割り切れるかどうか だけ確認すればよいとわかります。 ↩︎
これを知っていると、 $7 \times 11 \times 12 \times 13 = 12012$ などを一瞬で答えられるのでかっこいい！ ↩︎
$(50 + n)^{2} = 100 (25 + n) + n^{2}, (100 + n)^{2} = 100 (100 + 2 n) + n^{2}$ や、
一般に $(50 k + n)^{2} = 100 {(5 k)^{2} + k n} + n^{2}$ を用いると、わりと楽に平方の値を求められます ↩︎
$d$ 桁の数 $n$ の $1 0^{k}$ の位の数を $a_{k}$ とするとき、
$n = k = 0 \sum d - 1 a_{k} \times 1 0^{k} \equiv k = 0 \sum d - 1 a_{k} \times 1^{k} = k = 0 \sum d - 1 a_{k} (mod 3)$ 　となることから従います。 ↩︎
この記事において　 $\equiv (mod n)$ 　とは、「『 $n$ の倍数であるか』が両辺で一致している」ことを意味しています。「 $0$ か $0$ じゃないか」だけを区別する、ゆるい合同式とでもいいましょうか ↩︎
$1001, 2001$ に比べると少し計算が複雑なので、 $17, 19$ を個別にチェックしたほうが速いかもしれないですね…
（その場合、 $1003 = 17 \times 59, 1007 = 19 \times 53$ といった式が使えます） ↩︎
$163$ が素数であることを知っていれば、
$3187 \equiv (3187 \times 2) \equiv (6374 - 2001 \times 3) = 371 \equiv (2001 - 371) \equiv 163 (mod 23 \times 29)$
と、まとめて判定できます。 $2001$ を使うために、もとの数を2倍しているところがポイントですね ↩︎
筆者は一応 $4000$ くらいまでは記憶しているのですが、すぐに思い出せるのはせいぜい $1500$ くらいまでです。一般人レベルですね ↩︎
筆者が人力でチェックを通した最高記録は、 $20171129$ の素因数分解 $11 \times 17 \times 107867$ において登場した素因数 $107867$ に対する $317$ チェック（66 番目の素数）です。1時間くらいかかりました ↩︎