数をSOSU(素数)のかけざんに分解しようー素因数分解
#5
前回まで、SOSU(素数)について説明してきました。
今回紹介したいのは、素因数分解です。
素因数分解とは、「数を素数のかけざんの形に分解すること」です。
６を２×３、１２を２×２×３と表す、といった感じです。そんなに難しくないかと思います。
もし、素数のかけざんに分解できたら、それ以上細かい素数のかけざんでは表せません。
６の場合、２と３の２つの数のかけざんで表せますが、３つや４つの数のかけざんでは表せません。
６=２×３
６= ◯×△×□ とは表せない。
１が素数ではないことに注意しましょう。
同様に、１２も４つ以上の素数のかけざんでは表せません。
何はともあれ、素因数分解を理解するには実践が必要。以下の数を素因数分解してみてください。
８
１４
１７
３６
素因数分解のやりかたは、小さい素数から順番に割っていきます。
まずは２で割れるかどうか。割れるのであれば、何回割れるのか考えます。次は３、５、７と続いていきます。
偶数であれば、必ず１回は２で割れますよね。
さて、上記の数を分解するとこんな感じになります。
８=２×２×２
１４=２×７
１７
３６=２×２×３×３
１７は素数なので、これ以上分解できません。
つまり、素数でない数は必ず２つ以上の素数のかけざんに分解できるのです。
頭の体操になりましたか？
では、以下の数を素因数分解してくださいと言われたら、あなたはすぐにできますか？
２２１
３１３
８９７
３桁になると、なかなか難しいですよね。まず、数が素数かどうかすらわかりません。
前回の素数判定でも書いたように、大きい数になると「素数なのかどうか」を判定するのが難しくなります。
ちなみに上の答えは以下のようになります。
２２１=１３×１７
３１３
８９７=３×１３×２３
「２２１って１３で割れるのかよ、わかんねーよ！」と思った方。気持ちはよくわかります。素因数分解が難しいということをわかっていただけたのではないでしょうか？
大きな数になるほど、素因数分解は難しくなります。この「素因数分解の困難性」というのが、現在使われている「RSA暗号」というものに利用されているのです。
詳しいことは書きませんが、「素因数分解が難しいから、私たちのセキュリティーは守られている」と思っていただければ大丈夫です。
いかがでしたか？
小さい数字であれば素因数分解できそうですか？
身近には様々な数字があります。ときにはそういった数字に着目して、素因数分解してみるのも面白いです。ゲーム感覚でやってみてください！
最後まで読んでいただき、ありがとうございました。
【補足】素数に興味を持った方へ
「素数一覧」でググると、最初の小さい素数を調べることができます。
Instagramもご覧ください。毎日日付投稿をしています。
前の記事はこちら
次の記事はこちら
