素因数分解

素因数分解とは

●素因数分解とは、ある数を素数の積で表すことです。たとえば12は2×2×3、21は3×7です。簡単なことだと思いますか?　じゃあ、1001が 7 ×11×13であるとすぐにわかりますか？　これをコンピュータに計算させましょう。

数学でのやりかた

●素因数分解をするための簡単な公式はありません。数学者でもいちいち計算して行かなければなりません。でもこうすれば一番早いという手順があります。

●nを分解すべき自然数とします。まず，最初にnが2で割れるかどうか調べ，割り切れるときは2をメモしてnを2で割ったもので置き換えます。これをnが2で割り切れる間，繰り返し実行します。nが2で割れなくなったら割る数を3にして同様のことを繰り返します。次は4ですが、これは2のときに済んでいるのでやる必要がありません。次は割る数を5にして同様のことを繰り返せばよいのです。その次は7となります。

●4を考えなくてもいいのは、4=2×2だから、6を考えなくてもいいのは、6=2×3だからです。つまり素数だけをやっていけばいいのです。

●nが1になればメモしてある数字を並べたものが答えになります。

●たとえば90では、次のようになります。

n=90とする。
90÷2=45　　　　　　 →　 2
これ以上2で割れない→次の素数は３
45÷3=15　  　　　　 →　 3
15÷3= 5　  　　　　 →　 3
これ以上3で割れない→次の素数は５
 5÷5=1 　  　　　　 →　 5
1になったのでおわり。
よって、90=2×3×3×5

コンピュータでのやりかた

●ほとんど同じでいいのですが、「次の素数」をコンピュータに答えさせるのは難しいので，割る数は単に1を加算していくだけにします。こうすると無駄な計算もでます。たとえば、3の次は4ですが4で割れないのははっきりしています。2で割れるだけ割っているからです。でも無駄なだけで結果に影響を与えませんから不都合はありません。

割り切れるかどうか

●BASICには割り算をした余りをもとめる関数があります。mod(y,x) です。これは、y を x で割った余りをもとめます。たとえば、LET a = mod( 15, 6 ) とすれば、a には 3 が代入されます。割り切れるということはこれが 0 になるということです。

計画

●手順を書いてみます。２つあげますが、一つ目はあまりよい書き方ではありません。

あまりよくない整理の仕方
分解したい数を入力してもらう(n)
割る数を2にする(w)
割れるかどうかを判定する。←◆
　割れるなら、(w)を表示する。
　(n)を(n/w)にする。
　もう一度割れるかを判定する。(つまり◆にもどる)
　割れなければ(w)を次の数字にして、割れるかを判定する。
　(つまり◆にもどる)
ただし、(n)が１になったら終わり。

●このように IF THEN 〜 ELSE 〜 のような書き方をすると、繰り返しがやりにくくなります。DO 〜 LOOP は THEN の場合だけ繰り返すというような働きをしますから、それを意識します。次はよい例です。

よい整理の仕方
分解したい数を入力してもらう(n)
割る数を2にする(w)
(n)が１より大きいうちは繰り返す。
　　　割れるうちは繰り返す。
　　　　　(w)を表示する。
　　　　　(n)を(n/w)にする。
　　　繰り返しに戻る
　　　(w)を次の数字にする。
繰り返しに戻る

例２８

●上記の素因数分解のプログラムを完成させなさい。もちろん DO WHILE〜LOOP を２重に使います。IF文は必要ありません。検算のために２，３の計算例をあげておきます。

 1001  =  7  11  13 
 1003  =  17  59 
10001  =  73  137 
 9999  =  3  3  11  101

●このほかにも適当な数字を分解して、電卓で検算をしてみなさい。電卓は、[スタートメニュー]-[プログラム]-[アクセサリ] にあります。

●「割り切れるうちは」というのは、WHILE mod(y,x)=0 でかまいません。もちろん、LET a=mod(y,x) とやっておいて、WHILE a=0 でもいいですけど。