覚えておくと役に立つ！素数判定・素因数分解のテクニック

例えば、「367が素数か？」という問題が出てきたときに、恐らく多くの方が、

【最小の素数2から、一つずつ、しらみつぶしに当てはめていく】

という形で検討を進めるのではないでしょうか。
この方法で、全く問題ないのですが、1つ気になることがあります。それは、

しらみつぶしといえども、どこまで確認すればよいか　ということです。

まさか、2以上367未満の全ての自然数で割ってみるわけにはいきませんし、逆に、「2・3・4・5くらいまで調べて割り切れないので、多分素数だろう」、というのではあまりに乱暴です。

そこで、今回は、素数判定・素因数分解のテクニックとして、次の2つをご紹介します。

1つ目は、王道の方法として、「\((素数)^{2}\) が判定対象の数以下となる範囲で、小さい素数から1つずつ割り算してみる」という方法。

2つ目は、少々アクロバティックな方法として、「判定対象の数に近い、”キリがいい数” を考えて、\(({○}^{2}-{■}^{2})\) や、\(({○}^{3}\pm{■}^{3})\) の形を作る」という方法です。

これらの方法をマスターすれば、ある数が素数かどうかを判定するという場面（素数判定）だけでなく、「素因数分解」の場面でも非常に重宝します。

ぜひ、素数判定・素因数分解のテクニックを身に着けて、1秒でも速く・正確に計算できるようになりましょう！

なお、説明の都合上、「①王道→②アクロバティック」という順番に解説していきますが、実際に試験等で検討する際は、「②アクロバティック→①王道」という順番で検討することを強くおススメします。

その理由は、②の方が、

• 圧倒的に早く
• 計算ミスも少なくなる

からです。

解説

テクニック①　王道の方法（素数の2乗を考えて、小さい素数から1つずつ割り算する）

それでは始めていきます。

先に結論を言うと、「367」という数の場合は、「2」から「19」までの素数で割り算を考えてみて、割り切れなければ素数、ということになります。

なぜか？

それは、\({19}^{2}=361\) ，\({20}^{2}=400\) で、「19」は、\(p^{2}\leqq 367\) を満たす素数 \(p\) の内、最大のものだからです。

詳しく見ていきましょう。

まず、【「2」から「19」までの素数で割り算を考えてみて、割り切れなければ素数】には、2つの主張が含まれています。それは、

• 割り算をしてみるのは、素数だけでよい（素数判定を行うにあたっては、素数だけ確認すれば十分）
• 2乗した結果が、判定対象の数以下となる範囲で調べれば十分

次からは、これらの主張を個別に検討していきます。

1つ目の主張「割り算をしてみるのは、素数だけでよい」

「367」の約数の候補として、合成数 \(m\) を考えてみます。
※合成数とは、\(4=2\times 2\) や \(45={3}^{2}\times 5\) のような、2つ以上の数の積でできた数のことをいいます

もし、合成数 \(m\) が「367」の約数だとすると、「367」は、2以上の自然数 \(n\) を用いて

\[367=mn\]

と書けます。今、合成数 \(m\) が、素数 \(p\) と、2以上の自然数 \(k\) を用いて \(m=pk\) と書けるとすると、

\[367=mn=(pk)\cdot n=(kn)\cdot p\]

となり、合成数 \(m\) が「367」の約数だとすると、\(m\) の因数である素数 \(p\) も「367」の約数となることがわかります。

したがって、素数判定を行うにあたっては、素数だけ確認すれば十分、ということがわかりました。

2つ目の主張「2乗した結果が、判定対象の数以下となる範囲で調べれば十分」

「367」が「19」で割り切れるか調べる、というのは、「\(367=19\times n\)」を満たすような、2以上の自然数 \(n\) を見つけることと同じこと（同値）です。

そして、「19」は、\(p^{2}\leqq 367\) を満たす素数 \(p\) の内、最大のものなので、この \(n\) には、2～19までの素数（※）が入り得ます。
（※）1つ目の主張で見た、「素数判定を行うにあたっては、素数だけ確認すれば十分」を利用しています。

次に、「19」の次の素数「23」で割り算してみる、ということを考えます。
これは、「\(367=23\times n\)」を満たすような、2以上の自然数 \(n\) を見つけることと同値です。

そして、\(p^{2}\leqq 367\) を満たす素数 \(p\) の内、最大のものは「19」なので、この \(n\) には、23以上の数は入り得ません。（23を入れると、\({23}^{2}>367\) でオーバーしてしまう）

したがって、入り得るのは、2～19までの素数ですが、これは、既に、「19」までの割り算の方で確認済みです。そのため、追加で「23」で再検証を実施する必要はありません。

同様に、次の素数「29」以降でも、追加の検証は不要ということがわかります。

したがって、2乗した結果が、判定対象の数以下となる範囲で調べれば十分、ということがわかりました。

以上の検討より、素数判定・素因数分解の王道の方法としては、

\((素数)^{2}\) が判定対象の数以下となる範囲で、小さい素数から1つずつ割り算してみる

ということになります。

テクニック②　アクロバティックな方法（2乗-2乗、3乗±3乗の形を「無理やり」作る）

突然ですが、【「27000001」を素因数分解せよ】という問題が出たとき、みなさんならどうしますか？

まさか、①の王道の方法で、素数を小さいほうから1つずつ割ってみる、なんて、しませんよね。（この数は、2千7百万1なので、手計算ではほぼ無理です。。。）

では、この問題は歯が立たないのか、というと、実は、「2乗-2乗」「3乗+3乗」という形をうまく作ることで、素因数分解ができます。

「27000001」は、27000001=27000000+1　と分解できます。これを式変形していくと、

\[\begin{alignat*}{3}
27000001&=27000000+1 \\
&=27\times 1000000+1 \\
&={3}^{3}\times {10}^{6}+{1}^{3} \\
&={3}^{3}\times {100}^{3}+{1}^{3} \\
&={300}^{3}+{1}^{3}\qquad・・・(※1)\\
&=(300+1)({300}^{2}-300+1) \\
&=301\cdot\{({300}^{2}+2\cdot 300+1)-900\} \\
&=7\cdot 43\cdot\{{(300+1)}^{2}-{30}^{2}\} \quad・・・(※2)\\
&=7\cdot 43\cdot({301}^{2}-{30}^{2}) \\
&=7\cdot 43\cdot(301-30)(301+30) \\
&=7\cdot 43\cdot 271\cdot 331
\end{alignat*}\]

となり、無事に素因数分解できました！

この式変形の中で、（※1）で「3乗+3乗」を、（※2）で「2乗-2乗」の形を作っています。

ポイントは、【「無理やり」、2乗-2乗、3乗±3乗の形を作った】ということです。これにより、2乗・3乗の公式を利用して、うまく因数分解できました！

ちなみに、301・271・331の各数は、値が大きめで素数判定・素因数分解に少々手こずるかもしれません。

こちらは上でご紹介した、①王道の方法を利用すれば、比較的すぐに確認できると思いますので、復習がてら確認してみてください！

おわりに

今回は、素数判定・素因数分解における、考え方・計算のテクニックをご紹介しました。

②アクロバティックな方法の例としてご紹介した、「27000001」の変形を見ていただければわかるように、欲しい形を「無理やり」作る、というのは、少々慣れが必要になります。

特に、（※2）の

\[\begin{alignat*}{3}
&(300+1)({300}^{2}-300+1) \\
&=301\cdot\{({300}^{2}+2\cdot 300+1)-900\} \\
&=7\cdot 43\cdot\{{(300+1)}^{2}-{30}^{2}\} \quad・・・(※2)
\end{alignat*}\]

という変形は、かなりやりこまないと、なかなか思いつけないと思います。

一方で、このような、「どうしたらそんな変形が思いつくの！？」という式変形は、実は、大学の数学では、結構お目にかかることがあります。。。

ぜひ、なるべく多くの問題に触れ、このような式変形にも慣れていっていただけるとうれしいです！