2017年12月3日 | ブログ記事

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

youjo_tape

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

はじめに

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

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

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

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

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

素数判定をしよう

素数判定の基本

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

2,3,4,5,,997,998,999,10002, 3, 4, 5, \cdots, 997, 998, 999, 1000

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

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

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

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

1001=7×11×131001 = 7\times11\times13

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

素数判定のテクニック

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

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

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

77

3187318(318÷2)=159(159140)=19̸0    (mod 7)3187 \equiv 318 \equiv (318 \div 2) = 159 \equiv (159 - 140) = 19 \not \equiv 0 ~~~~ (\text{mod}~ 7)

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

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

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

31873187 を、77 で割り切れるかどうかが変わらないように小さくしていこう
1 桁目の 77 はもちろん 77 で割り切れるから、残りの 31831877 で割り切れるか調べればいいわけだ
31831822 で割って 159159、さらに 7×20=1407 \times 20 = 140 を減じて 1919、これは 77 では割り切れない
つまり、もとの数 3187318777 では割り切れないな!

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



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

7,11,137, 11, 13

3187(31871001×3)=18492    (mod 7×11×13)3187 \equiv (3187 - 1001 \times 3) = 184 \equiv 92 ~~~~ (\text{mod}~ 7 \times 11 \times 13)

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

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

17,1917, 19

3187(3187(100031)×3)=28028    (mod 17×19)3187 \equiv (3187 - (1000-31) \times 3) = 280 \equiv 28 ~~~~ (\text{mod}~ 17 \times 19)

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

3187(3187+23)=3210107̸0    (mod 23)3187 \equiv (3187 + 23) = 3210 \equiv 107 \not \equiv 0 ~~~~ (\text{mod}~ 23)

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

3187(31872900)=287(290287)=3̸0    (mod 29)3187 \equiv (3187 - 2900) = 287 \equiv (290 - 287) = 3 \not \equiv 0 ~~~~ (\text{mod}~ 29)

3131

3187(31873100)=87̸0    (mod 31)3187 \equiv (3187 - 3100) = 87 \not \equiv 0 ~~~~ (\text{mod}~ 31)

3737
3×37=1113 \times 37 = 111 であることがたまに役に立ちます(今回は使っていない)

3187(318737)=315063̸0    (mod 37)3187 \equiv (3187 - 37) = 3150 \equiv 63 \not \equiv 0 ~~~~ (\text{mod}~ 37)

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

3187(3187+41×3)(33141)29̸0    (mod 41)3187 \equiv (3187 + 41 \times 3) \equiv (331 - 41) \equiv 29 \not \equiv 0 ~~~~ (\text{mod}~ 41)

4343

3187(3187+43)(32343)28̸0    (mod 43)3187 \equiv (3187 + 43) \equiv (323 - 43) \equiv 28 \not \equiv 0 ~~~~ (\text{mod}~ 43)

4747

3187(318747)314(15747)11̸0    (mod 47)3187 \equiv (3187 - 47) \equiv 314 \equiv (157 - 47) \equiv 11 \not \equiv 0 ~~~~ (\text{mod}~ 47)

5353

3187(3187+53)324=182̸0    (mod 53)3187 \equiv (3187 + 53) \equiv 324 = 18^2 \not \equiv 0 ~~~~ (\text{mod}~ 53)

以上で、2,3,5,7,,532, 3, 5, 7, \cdots, 53 におけるチェックが全て通ったので、31873187 は素数です!

その他のテクニック

チェックを流用する

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

先ほど行った 318731877,11,137, 11, 13 チェックにおいて、

3187(31871001×3)=18492    (mod 7×11×13)3187 \equiv (3187 - 1001 \times 3) = 184 \equiv 92 ~~~~ (\text{mod}~ 7 \times 11 \times 13)

と計算しましたが、このことから、

3187=1001×323で割り切れない+   2×(22×23)23で割り切れる3187 = \underbrace{1001 \times 3}_{23 \text{で割り切れない}} +~~~ \underbrace{2 \times (2^2 \times 23)}_{23 \text{で割り切れる}}

に気づくことができれば、318731872323 では割り切れないとわかり、2323 のチェックは不要になります!

素数を覚える

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

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

因数分解公式を使う

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

518351837171 チェックにおいて、49001=69×714900 - 1 = 69 \times 71 を用いると、

5183(5183(49001))=2840    (mod 71)5183 \equiv (5183 - (4900-1)) = 284 \equiv 0 ~~~~ (\text{mod}~ 71)

と判定できます。

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

まとめ

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

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

明日の記事

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


  1. 素数大富豪、素数山手線ゲームなど ↩︎

  2. より一般には、整域(ある程度計算がうまくいく構造RR の元 pp について、「00 ではなく、逆元を持たず、a,bRa, b \in R に対して『ppabab を割り切るならば aa または bb を割り切る』」とき、pp素元 である、というようです
    (「逆元を持たない」という条件は、整数や複素整数などでは「1(とそれに相当するもの)は素数ではない」ことに相当し、実数や有理数などでは「素元が存在しない」ということを意味します。うまくまとまってますね)
    ちなみに、ここでは詳しく紹介しませんが、複素整数においては 2=(1+i)(1i)2 = (1+i)(1-i) が素数でなかったりして面白いです。今回の記事の内容として、このような「素数とは何か」「素数にはどんなものがあるのか」など、理論的な話をするか、今回のような実践的な話をするか、あるいは両方詰め込むか、かなり迷ったのですが、本記事の形に落ち着きました。 ↩︎

  3. nn が、ある素数ではない整数 a (1<a<n)a ~(1 < a < n) で割り切れるとします。
    すると、aa は素数ではないことから、aa を割り切る素因数 p (1<p<a)p ~(1 < p < a) が存在して、nnpp で割り切れます。つまり、「nnaa で割り切れる \Rightarrow nnpp で割り切れる」が成り立ちます。
    これは、nn が 素数ではない数 a (<n)a ~(< n) で割り切れるなら、nn が 素数 p (<n)p ~(< n) でも割り切れることを意味しているので、nn が素数であるか調べるためには、nn 未満の素数で割り切れるかどうか だけ確認すればよいとわかります。
    ㅤㅤ
    次に、nn が、ある整数 a (n<a<n)a ~(\sqrt n < a < n) で割り切れるとします。
    このとき、na\displaystyle \frac n a は整数となるので、この整数を b=nab = \displaystyle \frac n a とおくと、aa がとりうる値の範囲から、1<b<n1 < b < \sqrt n が従います。また、nb=a\displaystyle \frac n b = a なので、nnbb で割り切れることがわかります。これにより、「nnaa で割り切れる \Rightarrow nnbb で割り切れる」が成り立ちます。
    これは、nna (>n)a ~(> \sqrt n) で割り切れるなら、nnb (<n)b ~(< \sqrt n) でも割り切れることを意味しているので、先の議論と合わせると、nn が素数であるか調べるためには、n\sqrt n 未満の素数で割り切れるかどうか だけ確認すればよいとわかります。 ↩︎

  4. これを知っていると、7×11×12×13=120127 \times 11 \times 12 \times 13 = 12012 などを一瞬で答えられるのでかっこいい! ↩︎

  5. (50+n)2=100(25+n)+n2,(100+n)2=100(100+2n)+n2(50+n)^2 = 100(25+n) + n^2, (100+n)^2 = 100(100+2n) + n^2 や、
    一般に (50k+n)2=100{(5k)2+kn}+n2(50k+n)^2 = 100\{(5k)^2 + kn\} + n^2 を用いると、わりと楽に平方の値を求められます ↩︎

  6. dd 桁の数 nn10k10^k の位の数を aka_k とするとき、
    n=k=0d1ak×10kk=0d1ak×1k=k=0d1ak (mod 3)\displaystyle n = \sum _{k=0}^{d-1} a_k \times 10^k \equiv \sum _{k=0}^{d-1} a_k \times 1^k = \sum _{k=0}^{d-1} a_k ~(\text{mod}~ 3) となることから従います。 ↩︎

  7. この記事において (mod n)\equiv (\text{mod}~ n) とは、「『nn の倍数であるか』が両辺で一致している」ことを意味しています。「0000 じゃないか」だけを区別する、ゆるい合同式とでもいいましょうか ↩︎

  8. 1001,20011001, 2001 に比べると少し計算が複雑なので、17,1917, 19 を個別にチェックしたほうが速いかもしれないですね…
    (その場合、1003=17×59,1007=19×531003 = 17 \times 59, 1007 = 19 \times 53 といった式が使えます) ↩︎

  9. 163163 が素数であることを知っていれば、
    3187(3187×2)(63742001×3)=371(2001371)163    (mod 23×29)3187 \equiv (3187 \times 2) \equiv (6374 - 2001 \times 3) = 371 \equiv (2001 - 371) \equiv 163 ~~~~ (\text{mod}~ 23 \times 29)
    と、まとめて判定できます。20012001 を使うために、もとの数を2倍しているところがポイントですね ↩︎

  10. 筆者は一応 40004000 くらいまでは記憶しているのですが、すぐに思い出せるのはせいぜい 15001500 くらいまでです。一般人レベルですね ↩︎

  11. 筆者が人力でチェックを通した最高記録は、2017112920171129 の素因数分解 11×17×10786711 \times 17 \times 107867 において登場した素因数 107867107867 に対する 317317 チェック(66 番目の素数)です。1時間くらいかかりました ↩︎

この記事を書いた人
youjo_tape

'17 / 37 / 養生テープ

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2017年11月30日
Negative Thinking
phi16
2017年11月14日
IBIS2017参加報告
Keijan
2017年11月8日
数学と仲良くなりたい人へ
60
2017年11月2日
積分ってなんだろう?区分求積法からリーマン積分へ
Azon
2017年12月27日
Splatoon2~ボムの使い方~
shigurure
2017年12月26日
RustでMCMC(Metropolis-Hasting)
David

活動の紹介

カテゴリ

タグ