素因数分解のやり方

素因数分解は、約数で割っていけばよいです。しかし約数を見つけるのに手間がかかります。

本来、素因数分解は難しい問題で簡単に分解できないがゆえに、その事を利用し暗号処理等に利用されているのです。簡単にできる代物ではないのです。

そうはいっても、素因数分解が必要な局面は生じます。例えば、最小公倍数を求めるときなど、素因数分解できれば簡単に求められます。

そこで、素因数分解を上手に行うためのコツを示します。簡単にいうと、割りやすい数字でできるところまで割って割って、少しでも数字を小さくしてから別の素因数(約数)を探す手順となります。

ステップ1.
すぐに、割れると判断できる数があればそれで割る

代表的なのは、10です。

その他にも問題文や条件などから、なんかの数で割り切れているとわかる場合にはその数で割ります。

割ることで商が小さくなり素因数分解しやすくなります。

 

ステップ2.
2で割り切れるだけ割る

1の位が偶数なら2で割り切れます。割り切れなくなるまで(1の位が奇数になるまで)割り続けます。

例。436は1の位が6で偶数なので2で割り切れます。2で割って、218を素因数分解します。

 

ステップ3.
5で割り切れるだけ割る

1の位が5の場合は5で割り切れます。5で割り切れなくなるまで割り続けます。これは例を出すまでもないでしょう。85などはまず5で割って考えます。

 

ステップ3.
3または9で割り切れるだけ割る

各桁を合計して3または9で割り切れる場合は、3または9で割り切れます。3で割り切れなくなるまで割り続けます。

例えば、1899を素因数分解する場合、1+8+9+9=18で、18は9で割り切れます。ですから、1899は9で割り切れます。その商は、211となりますが、各桁を足すと2+1+1=4となります。4は3で割り切れないので211は3で割り切れないことがわかります。

 

ステップ4.
7で割り切れるだけ割る

実際に7で割り算して割り切れるか調べます。ちょっと面倒ですが、1桁の割り算なので余白のメモで計算できます。

 

ステップ5.
11で割り切れるだけ割る

11で割り切れるかどうかは、1位から上の位に引き算と足し算を交互にやってその結果が11で割り切れるか調べます。

例えば、2321の場合、1-2+3-2=0なので11で割り切れます(0は割り切れる数と考えます)。ですから、2321は11で割り切れることがわかります。11で割り切れなくなるまで割り続けます。

 

補足

ステップ5までやれば、200ぐらいまでの数は素因数分解できます。普通のテストではこれだけの計算力で太刀打ちできます。

 

さらに、平方数、100までの素数、2のべき乗などの数を覚えておくと、1000ぐらいまではなんとか素因数分解できます。500以上の数がでてくると、ちょっと間違うかもしれませんが、慎重にやればできるはずです。

ステップ5以降は、ひたすらエラトステネス方式で小さな素数で試し割りを続けていきます。

√1000<32ですから、13から31までの素数で試し割りすると1000までの自然数の素因数分解は確実にできます。

言い忘れましたがもちろん、約数だとか、掛け算九九は知っているという前提でここまで書いていますy。

なにをかくそう、素因数分解で一番威力を発揮するのは、掛け算九九です。九九が暗唱できれば100までの素因数分解は簡単にできるはずです。

 

九九にでてくる数以外に覚えておいたほうがよい数としては、平方数、2のベキ(できれば3のベキも)、100までの素数、これが頭に入っていると素因数分解だけでなく、いろいろと計算する上で役に立ちます。

 

平方数

112=121
122=141
132=169

これは3平方の定理でもよくでてくる数ですから、覚えておいた方がよいです。

 

2のベキ乗数

どんどん2倍する数列は覚えましょう。情報処理の計算でもよくでてきます。

1,2,4,8,16,32,64,128,256,512,1024

210=1024
は有名です。

 

100までの素数

覚えておかなくても、頭で素数判定できるぐらいは最低しておきます。

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

91など80より上の数は九九にでてこないのでちょっと注意です。

グロタンディーク素数と呼ばれている57は素数ではありません。3で割り切れます。

 

最後に

もちろん、これだけ押さえておけばよいというわけではありません。

可能ならもっとたくさんの数について素因数分解できるに越したことはありません。

私は計算が得意な方ではありませんが、過去に受けたテスト問題などは、この方法でなんとか対処できました。

なお、数学オリンピックは別格です。オリンピック選手には、ここに書かれていることは常識であって、さらにもっと上級レベルの計算力が要求されます。

 

 

 


 

 

[ad#foot]