人力素数判定をしよう！
みなさんこんにちは。倍数判定の時間です。
素数大富豪をしているとき、あるいは街中で見つけた自然数が素数かどうか気になったとき。私たちが日常生活を送るうえで、倍数判定力（素数判定力）を問われる局面は多々あると思います。今日は私がそのような場面でどのように考え、どのように素数と出会っているかを紹介するため、倍数判定法の記事を書きます。
与えられた自然数nが素数かどうかを人力で判定するとき、√n以下の素数で割ってみる「試し割り」以外に有用な方法はほとんどないでしょう。「素数pで割れるかどうか」は「素数pの倍数かどうか」と同じことなので、実際には素数の倍数判定が重要になってくるわけです。小さい素数から順に、倍数判定法を見ていきましょう。
2,3,5の倍数判定 ～一の位チェック＆桁和チェック～
一の位が偶数なら元の数も偶数であり、一の位が5か0なら5の倍数です。また各桁の和が3の倍数なら元の数も3の倍数です。
例：5123874は2の倍数。83025は5の倍数。また5+1+2+3+8+7+4=30と8+3+0+2+5=18は3で割れるので、この二数は3の倍数でもある。
〈追記〉
要は、一の位が1,3,7,9のいずれかでないと2か5で割れてしまいます。
また、3の倍数判定については「桁和が3で割れるか否か」をチェックできればいいので、
・3の倍数の部分が見えたら消す
・等差数列をなす三整数は消す
を使うと早いです。たとえば458881479は、先頭の45と末尾の9を消すと888と147という二つの等差数列が残るので3の倍数です。
7,11,13の倍数判定 ～1001チェック→91＆交代和チェック～
7*11*13=1001なので、判定したい自然数nから1001の倍数を引いても、「7の倍数かどうか」「11の倍数かどうか」「13の倍数かどうか」の性質は変わりません。さらにここから7と13の倍数判定については、7*13=91の倍数を引いていって確かめることができます。また、nの偶数桁の和と奇数桁の和との差を計算して11で割れるかどうか確かめれば、nが11の倍数かどうかを確かめたことになります（証明は略）。
例：3157から1001*3=3003を引くと154であり、154から91を引くと63である。63は7では割れて13では割れない。また154の偶数桁は5のみで奇数桁の和は1+4=5であり、5-5=0は11の倍数。よって3157は7と11の倍数であり13の倍数ではない。
7*11*13が1001であることには数の神秘を感じずにはいられません。なお、91を使った倍数判定は今年1月にtsujimotter氏により見出されました。
ここまでは、素数大富豪プレーヤーをはじめとする多くの方がご存知の手法かと思います。本題はここからです。
〈追記〉
特に6桁の数を判定したい場合、「上3桁と下3桁の差を計算する」ことが「1001の倍数を引く」操作になっているので、上3桁と下3桁が近い数のときは1001チェックはとても早く終わります。例えば108109は上下の差が1なので7,11,13では割れません。
108のような2,8で終わる3桁の3の倍数の下に一つ違いの数を付けると13以下の素因数を持たない整数となり、素数の期待が高まります。その中で
・102101,102103
・108107,108109
・192191,192193
・312311,312313
・342341,342343
・522521,522523
・612611,612613
・822821,822823
・882881,882883
は双子素数です。闘会議をきっかけに調べてみました。
twitter.com本日のハイライト！ 108109は素数でした！しかも108107も素数！覚えやすい上に双子素数！！ #素数大富豪 #素数大富豪in闘会議 #闘会議2017 #闘会議 pic.twitter.com/LOlR4zNKpS
— 狡猾な狐@617伝道師 (@wreck1214) 2017年2月12日
17以上の倍数判定① ～3p法～
これは私が17以上の倍数判定をする際に最もよく使っている方法です。簡単に言うと「自然数nに素数pまたはその三倍（3p）を足すか引くかして一の位を0にする」方法で、以下の事実に基づいています。
つまり、pや3pを使えば一の位を0にできるのです。一の位の0は取って考えてよい（7以上の素数pについて、「10で割る」という操作は「pの倍数かどうか」には影響しない）ので、これで桁数を一つ減らせたことになります。
そして、桁を減らした後の数が2や5で割れるなら、一の位が1,3,7,9になるまで割りましょう。そうすれば再び3p法を適用できます。
例：1121から17*3=51を引くと1070であり、0を取った107は素数なので17で割れない。しかし1121に19を足すと1140であり、0を取った114は2で割ると57である。これは19*3である。よって1121は17の倍数ではないが19の倍数である。
17以上の倍数判定② ～概数法～
これは、判定したい自然数nの上3桁くらいを見てpの倍数が思い浮かんだときに有効な方法です。3p法に比べると自明なやり方ですが、うまく使い分けるとスピードが上がります。3p法が「下の位から攻める」のに対して、概数法は「上の位から攻める」方法です。
例：1021は4桁の数だが、上3桁を見ると102であり、102は17の倍数である。よって1020が17の倍数であり、1を加えた1021は17の倍数ではない。
さて、紹介する倍数判定法は以上ですが、最後にここまでの内容を踏まえて、1187が素数であることを確かめる手順の一例を解説します。
- 1187の一の位は7なので、2,5では割れない。また桁和は1+1+8+7=17なので3の倍数でもない。（一の位チェック＆桁和チェック）
- 1187から1001を引くと186であり、186から91を2回引くと4が残る。当然4は7や13では割れない。また186の偶数桁和は8、奇数桁和は1+6=7であり、8-7=1は11で割れない。（1001チェック→91＆交代和チェック）
- 1187から17を引くと1170であり、0を取った117から再び17を引くと100なので17では割れない。また1187から19*3=57を引くと1130であり、0を取った113は素数なので19で割れない。（3p法）
- 115は23の倍数、116は29の倍数である。1187-1150=37は23で割れず、1187-1160=27は29で割れない。（概数法）
- 1187に31*3=93を足すと1280であり、これは見るからに2,5以外の素因数を持たず31で割れない。（3p法）
37^2>35^2=1225>1187なので、ここまでで1187が素数だと分かったことになります。
なお、17以上の素数の倍数判定については、29など簡明な方法が見つかっているものもあります。
これらを併用できればより効率よく素数判定を進められるかもしれません。
それでは今日はこの辺で。
