高速に暗算で素数判定する方法を晒してみる

そういえば、最近めっきり暗算で素数判定をしていません。それどころか生活の中で電卓を使う機会が少しずつ高まっている実感があり、いよいよ歳を重ねたことを意識せざるを得ない日々を過ごしています。

 

かつては、車の運転中に眠くなったときに前を走っている車のナンバーを素数判定して、4桁の素数を見つけた時に自然と上がるテンションを利用して眠気を覚ましたりなどよくしたものですが、最近では車を運転する機会も減り、そもそも日中眠くなることも少なくなり、余計に素数判定から遠い生活を送っています。

 

さて、そんな僕ではありますが、いざ素因数分解をすると「速っ!」と驚かれることがしばしばあります。特に速いつもりは無いのですが、素数素人の方々から見ると割りと速いのかもしれません。そこで、今回の記事では「僕が4桁の自然数を素因数分解する手順」を赤裸々に語ってみたいと思います。一体誰が得をするのかわかりませんが、昨今の素数ブーム(※)を見るに、意外とニーズがあろうと踏んで書くことにしました。

(※ そんなものはありません)

 

なお、普段は素数に興味の無いような顔をしているのに、素数の話をするとちょっと楽しそうにする人っていますよね。僕は彼らのことを「隠れ素数好き」と呼んでいますが、実は世の中には隠れ素数好きが多いことを僕は知っています。「素数のことをあまりよく知らないから、興味はあるけど素数好きを名乗れない…(モジモジ)」という恥じらいが邪魔をしているのかもしれませんが、そんなものは捨てて、是非素数好きを名乗りましょう。

 

 

閑話休題。

 

 

では、僕が行っている(4桁以下の自然数に対する)素因判定の暗算アルゴリズムを紹介します。

 

 

1. 100以下の素数を全て(25個)暗記する。

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

の25個ですが、基本的には九九に出てこない奇数は素数の可能性が高く、間違えやすいのは91(7*13)くらいでしょうか。他は素数ではないことが自明なものばかりです。まぁとりあえずこれらは暗記です。(暗記しないと計算すべき回数が増えてしまうので、損してしまいます。)

 

これらの素数を見かけたら「あ、これは素数だ。なぜなら覚えているから。」でおしまいですので、以降は100以上の自然数に対して素数判定を試みるものとします。

 

 

2. 偶数と5の倍数は無視。

当たり前ですね。

 

 

3. 3の倍数は無視。

これも当たり前ですが、ある自然数nが3の倍数かどうかを見分けるには「各桁の和が3の倍数の時に限り、nは3の倍数」という事実を使います。例えば9729という自然数であれば、9+7+2+9=27という計算をするだけで、「あぁ、3の倍数だな」と判定できます。

実際には、脳内では、両端の9は3の倍数なので無視して、7+2のみ計算すれば十分です。

 

 

4. 7の倍数か否かを判定する。

ここで少し難易度が上がりましたね。でも実は簡単です。一般的に割り算を暗算でやるのは大変なことだとは思いますが、一方で「割った余りがゼロか否かのみを判定する」ことは実はそんなに大変ではないのです。例えば、8591という自然数が7で割り切れるかどうかを考えてみましょう。まず、7000(7の倍数)を引いて1591について考えれば良いことがわかります。なぜなら、任意の整数から7の倍数を加減しても、7で割った余りは変わらないからです。同様に、1591から1400(7の倍数)を引いて191とします。次に、210(7の倍数)から191を引いて19として、19は7の倍数ではないので、結論として8591は7の倍数ではないと判断できます。

最後の方で210から191を引いたのは7の倍数を加減しているわけではありませんので余りは変わり得ますが、余りがゼロか否かは不変ですので、問題ありません。このテクニックを使うと素数判定が速くなります。

 

 

5. 11の倍数か否かを判定する。

これは7の倍数よりは簡単で、判定したい自然数の奇数桁目の和偶数桁目の和が11の倍数かどうかを判定すれば良いだけです。

例えば4829は、4+2=6、8+9=17、となり、6と17の差は11の倍数なので、4829は11の倍数と判定できます。

 

 

6. 13の倍数か否かを判定する。

7の倍数の時と同様に、足し算と引き算だけで判定します。例えば7559という数字は、7800(13の倍数)から引いて241、260(13の倍数)から引いて19、19は13の倍数ではないので、結果7559は13の倍数ではないと判定できます。この方法であれば、13の倍数か否かの判定が3秒もかからずに計算可能です。

 

7. 以降、17、19、23…と順に97までの素数について、倍数か否かを判定する。

もはやゴリ押しです。ただ、素数判定したい自然数の平方根以下の素数についてのみ考えれば十分です。例えば、2017を素数判定しようと思ったら43まで割れば良いので、2,3,5,7,11,13,17,19,23,29,31,37,41,43の14回の倍数判定をすれば良く、上記のように簡単に倍数判定できる2,3,5,11を除けば、たった10回の倍数判定をすれば素数判定ができてしまうのです。

もし平方根が正しく求められなくて47で割ってしまっても、無駄ではありますが問題はありません。50以上の素数で割る必要が無いことは、50の2乗が2500で2017より大きいことからすぐに判断できるかと思います。

実際にやってみると、2017は

(2,5)2の倍数でも5の倍数でもない。

(3)2+1+7=10なので3の倍数ではない。

(7)2100から引いて83、83は7の倍数ではない。

(11)2+1=3、7との差は4なので11の倍数ではない。

(13)1300を引いて717、650を引いて67、67は(素数なので)13の倍数ではない。

(17)1700を引いて317、340から引いて23、23は(素数なので)17の倍数ではない。

(19)1900を引いて117、95を引いて22、22は19の倍数ではない。

(23)2300から引いて283、230を引いて53、53は(素数なので)23の倍数ではない。

(29)2900から引いて883、870を引いて13、よって29の倍数ではない。

(31)1860を引いて157、155を引いて2、よって31の倍数ではない。

(37)2220から引いて203、222から引いて19、よって37の倍数ではない。

(41)2050から引いて33、よって41の倍数ではない。

(43)2150から引いて133、129を引いて4、よって43の倍数ではない。

 

以上より、素数であることがわかります。これらの計算は掛け算と足し算引き算のみを使っているに過ぎないため、割り算をやるよりは高速に素数判定できます。

 

 

 

というわけで、以上が僕の素数判定方法でした。もしもっと効率的に暗算する方法があれば、是非コメントやご連絡いただけると嬉しいです。(本当は1万以下の素数を全て暗記したいなぁとは思っているのですが…。)