素因数分解

素因数分解とは、数値を構成する素数を求める（素数の累乗の和で表す）ことです。例えば、９８なら2×7² と表されます。中学校や高校の数学の基本事項の一つですね。

素因数分解のアルゴリズム

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

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

こうして、２で割り切れなくなるまで同じ処理を繰り返せば、その数に素因数として「2」がいくつ含まれるかわかるわけです。2で割り切れなくなったら、3以上の数についても同じ処理をします。

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

素因数分解のプログラム

以上のアルゴリズムをJavaScriptのプログラムにまとめると、以下のような素因数分解を行う関数を作ることができます。

素因数分解の数式は素因数の累乗から構成されるので、素因数と累乗の数値をプロパティに持つオブジェクトの配列を返す形にしてみました。

/*
	引数:n-素因数分解する整数
	値:nの素因数分解（{num:素因数, r:指数}を持つオブジェクト配列）
*/
function primeFactorization(n) {

	// 平方根を保存
	var s = Math.floor(Math.sqrt(n));

	var r = 0;

	var result = Array();

	// 2から平方根までの素因数を求める
	for (var i = 2;i <= s;i++) {

		if ((n % i) == 0) {

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

			do {

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

				n = n / i;

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

			// 素因数iを指数とともに保存
			result.push({num:i, r:r});

		}

	}

	// 残った素数を追加
	if (n > s) {
		result.push({num:n, r:1});
	}

	return result;

}

まとめとして、この関数を使って素因数分解を行い数式として表示するサンプルプログラムを作ってみました。

=
素因数分解

入力欄に数値（2以上の整数）を入れてボタンをクリックすると、素因数分解を行います。