feature image

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

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

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

はじめに

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

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

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

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

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

素数判定をしよう

素数判定の基本

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

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

実は、ある数 が素数かどうか判定するには、「 以下の素数で割り切れるかどうか」さえ確かめればよい、という事実があります[3]
これを踏まえると、 が素数であるかどうかを調べるには、 なので、 以下の素数:

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

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

素数判定のテクニック

次に、少し難度を上げて、 の素数判定をしてみるとともに、素数判定のテクニックを紹介していきます。
まず、[5] であることから、 という 16 個の素数についてチェックすればいいとわかります。
順に見ていきましょう。


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


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

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

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

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

を、 で割り切れるかどうかが変わらないように小さくしていこう
1 桁目の はもちろん で割り切れるから、残りの で割り切れるか調べればいいわけだ
で割って 、さらに を減じて 、これは では割り切れない
つまり、もとの数 では割り切れないな!

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



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

さきほど出てきた を使いました。この他にも、例えば:

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


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


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


であることがたまに役に立ちます(今回は使っていない)


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

以上で、 におけるチェックが全て通ったので、 は素数です!

その他のテクニック

チェックを流用する

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

先ほど行った チェックにおいて、

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

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

素数を覚える

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

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

因数分解公式を使う

の形をした素数のチェックでは、 を考えると計算しやすいときがあります。

チェックにおいて、 を用いると、

と判定できます。

これと似たテクニックとして、 の形をした素数のチェックで が使えるかもしれないですが、筆者は使ったことがないです

まとめ

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

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

明日の記事

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


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

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

  3. が、ある素数ではない整数 で割り切れるとします。
    すると、 は素数ではないことから、 を割り切る素因数 が存在して、 で割り切れます。つまり、「 で割り切れる で割り切れる」が成り立ちます。
    これは、 が 素数ではない数 で割り切れるなら、 が 素数 でも割り切れることを意味しているので、 が素数であるか調べるためには、 未満の素数で割り切れるかどうか だけ確認すればよいとわかります。
    ㅤㅤ
    次に、 が、ある整数 で割り切れるとします。
    このとき、 は整数となるので、この整数を とおくと、 がとりうる値の範囲から、 が従います。また、 なので、 で割り切れることがわかります。これにより、「 で割り切れる で割り切れる」が成り立ちます。
    これは、 で割り切れるなら、 でも割り切れることを意味しているので、先の議論と合わせると、 が素数であるか調べるためには、 以下の素数で割り切れるかどうか だけ確認すればよいとわかります。 ↩︎

  4. これを知っていると、 などを一瞬で答えられるのでかっこいい! ↩︎

  5. や、
    一般に を用いると、わりと楽に平方の値を求められます ↩︎

  6. 桁の数 の位の数を とするとき、
     となることから従います。 ↩︎

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

  8. に比べると少し計算が複雑なので、 を個別にチェックしたほうが速いかもしれないですね…
    (その場合、 といった式が使えます) ↩︎

  9. が素数であることを知っていれば、

    と、まとめて判定できます。 を使うために、もとの数を2倍しているところがポイントですね ↩︎

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

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

youjo_tape icon
この記事を書いた人
youjo_tape

'17 / 37 / 養生テープ

この記事をシェア

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

関連する記事

2017年11月14日
IBIS2017参加報告
Keijan icon Keijan
2017年11月17日
そばやのワク☆ワク流体シミュレーション~MPS編~
sobaya007 icon sobaya007
2017年12月26日
RustでMCMC(Metropolis-Hasting)
David icon David
2017年12月13日
チズケ破壊論
whiteonion icon whiteonion
2017年12月1日
WaltZ
Double_oxygeN icon Double_oxygeN
2017年11月4日
文章をよしなに分散表現しよう
David icon David
記事一覧 タグ一覧 Google アナリティクスについて