素因数分解

素因数分解とは

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

数学でのやりかた

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

nを分解すべき自然数とします。まず,最初にnが2で割れるかどうか調べ,割り切れるときは2をメモしてnを2で割ったもので置き換えます。これをnが2で割り切れる間,繰り返し実行します。nが2で割れなくなったら割る数を3にして同様のことを繰り返します。このあとさらに 5,7,11,13... と素数で割っていきます。そして、nが1になればメモしてある数字を並べたものが答えになります。

4を考えなくてもいいのは、2で割れなくなっているので 4=2×2 で割れないことがはっきりしているからです。同様に 6 を考えなくてもいいのは、6=2×3だからです。つまり素数だけをやっていけばいいのです。

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

n=90とする。
90÷2=45       →  2
これ以上2で割れない→次の素数は3
45÷3=15        →  3
15÷3= 5        →  3
これ以上3で割れない→次の素数は5
 5÷5=1         →  5

1になったのでおわり。
よって、90=2×3×3×5

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

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

割り切れるかどうか

割り算をした余りをもとめ、割り切れるときにはこれが 0 になるということを利用します。

計画

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

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

このように if ~ else ~ のような書き方をすると、繰り返しがやりにくくなります。while ~ は if の条件が成立する場合だけ繰り返すというような働きをしますから、それを意識します。

問題をよく考えると2つの繰り返しがあることがわかります。割り切れるうちは繰り返すと、n が1より大きいうちは繰り返すという2つです。次はよい例です。

よい整理の仕方
分解したい数を決める(n=xx ;)
割る数を2にする(w=2;)
(n)が1より大きいうちは繰り返す。( { が必要)
      割り切れるうちは繰り返す。( { が必要)
          (w)を表示する。
          (n)を(n/w)にする。
      繰り返しの終わり( })
      (w)を次の数字にする。
繰り返しの終わり( })

課題

上記の素因数分解のプログラムを完成させなさい。もちろんwhile ~ を2重に使います。if文は必要ありません。

ファイル名 Soinsuu.java

「割り切れるうちは」というのは、while ( y%x == 0 ) でかまいません。もちろん、a=y%x とやっておいて、while (a==0) でもいいですけど。(もちろん x, y はこの問題に合わせて変えます)

検算のために2,3の計算例をあげておきます。

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

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


Javaプログラミング
聖愛中学高等学校
http://www.seiai.ed.jp/
Feb.2009