素因数分解

素因数分解とは、数値を素数の積で表す事です。例えば、９８なら2×7² と表されます。中学校や高校の数学の基本事項の一つですね。

この素因数分解のアルゴリズムとして最も簡単なのは、その数を２からその数値の平方根までの整数で順次割って行く、という計算法でしょう。なぜ、平方根までかというと、ある整数を整数の積の形で表す時に平方根が含まれていれば、残りの数は必ず平方根以下になるからです。

まず、素因数に分解する正の整数a を２で割ってみます。２で割り切れれば、その数は２を因数に持つわけですから因数のリストに２を加えます。そして、aを２で割った数値をaに代入してさらに２で割ってみます。これで割り切れれば、因数のリストにまた２を加えます（この場合、a は2²=4を因数に持っているわけです）。

こうして、２で割り切れなくなるまで同じ事を繰り返しましょう。２で割り切れなくなったら、３以上の数についても同じ事をします。

なお、この方法では因数のリストはすべて素数になります。なぜなら、割り切れるか確認する時に割り切れなくなるまで処理を繰り返しているので、現在調べている数より小さな数では割り切れない事が保証されているからです。

プログラム例としては、こんな感じです。因数のリストは直接文字列s に書き込んでいます。

r=(int)Math.sqrt(a);

s=new String();

for (i=2;i<=r;i++) {

    if ((a % i)==0) { // 割り切れるか調べる

        n=0; // 指数カウンタクリア

        do {

            n++; // 指数カウンタプラス

            a=a/i;

        } while ((a % i)==0);

        if (n==1) // 因数リスト更新
            s=s+"*"+String.valueOf(i);
        else if (n>1) // 割り切れた回数を指数で表現
            s=s+"*"+String.valueOf(i)+"^"+String.valueOf(n);

    }

}

if (a>r) // 残った素数を追加
    s+="*"+String.valueOf(a);

s=s.substring(1); // 先頭の*を除去

このプログラムでは、割り切れた数を数えて（指数カウンタ）、指数形式の表示にしています。また、最後に割り切れずに残った素数をリストに加えるのも忘れないようにしましょう。

プログラムソース表示

テキストフィールドに適当な正の整数を入れてG o!ボタンをクリックしてください。^は指数を表す記号です（例－3^2=3²）