最小公倍数を求める

先に素因数分解を使って最大公約数を求めてみたので、今度は最小公倍数を求めてみましょう。

最小公倍数とは

最小公倍数とは、ある整数aとbの共通の倍数のうち最小となるものです。略してLCMという表記が広く使われています。

たとえば、5と3に共通する倍数、公倍数には15、30、45・・・などがあり、このうち最小となる最小公倍数は15です。この場合は、互いに素(素数同士)なのでたまたまかけあわせた数になっています。

もちろん、二つの数が「共通の因数」を持つ場合は単純な積が最小公倍数にはなりません。たとえば6と9なら、最小公倍数は18(6*3、9*2)となるわけです。

最小公倍数を求めるアルゴリズム

では、具体的に(素因数分解に基づいて)二つの整数の最小公倍数を求めるアルゴリズムを考えてみましょう。

まず最小公倍数は、それぞれの数の倍数なので「それぞれの数の素因数そのもの」が含まれることは明らかですね。そして「共通」の倍数という性質から、一方にのみ含まれる素因数の要素(因数)があれば、その因数がすべて最小公倍数の因数に含まれることも明白です。

ここで注意すべきは、共通に含まれる因数のうち「最大の指数」を持つものを含める、ということです。

たとえば、12と9には共通の因数として3が含まれます。

このうち12を素因数分解すると、4*3で3の指数は「1(3が1回だけ出てくる)」、9は3*3ですので3の指数は「2」となります。そして、12と9の最小公倍数36には当然「3」が因数として含まれますが、その指数は1と2の多い方で「2」となる(36=4*3*3)わけですね。

以上のことから、aとbの最小公倍数を素因数分解すると

aとbに共通に含まれる因数
aとbいずれかに含まれる因数

から構成されることになるでしょう。アルゴリズムとしてみると、これらを掛け合わせれば最小公倍数になるわけです。

最小公倍数を求めるプログラム

では、この最小公倍数を求めるアルゴリズムを実際にJavaScriptのコードで実装してみましょう。

まずやるべきことは、整数aとbの素因数分解です。とりあえず、素因数分解の回で使ったアルゴリズムそのままに「素因数分解結果のオブジェクト配列を返す」JavaScript関数getPrimeList()を作ってみましょうか。

今回の素因数分解では、指数(その素因数が何回出てくるか)も重要なので、各要素をその数値(num)と指数(r)をプロパティに持つJavaScriptのオブジェクトにしてみました。

// numを素因数分解し結果を因数と指数のオブジェクト配列として返す
function getPrimeList(num) {

	var list = new Array();

	if (num < 1) {
		return null;
	}

	var i;

	// 平方根を素因数候補の最大値とする
	var r = Math.floor(Math.sqrt(num));

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

		// 候補で割り切れたら素因数として追加
		if ((num % i) == 0) {

			var n = 0;

			// 割り切れる回数を指数として記録
			do {

				n++;

				num = num / i;

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

			// 素因数オブジェクト作成
			var item = new Object();

			// 値と指数をプロパティとして記録
			item.num = i;
			item.r = n;

			// 配列にオブジェクトを記録
			list.push(item);

		}

	}

	// 最後に残った素因数を追加
	if (num > r) {

		var item = new Object();

		item.num = num;
		item.r = 1;

		list.push(item);

	}

	// 結果を返す
	return list;

}

次に、この関数を使って二つの整数の最小公倍数を求める関数getLCM()を作ります。

これは、配列に格納されているそれぞれの数の素因数に対して先に組み立てたアルゴリズムをそのまま適用するだけですね。

// 整数aと整数bの最小公倍数を求める
function getLCM(a, b) {

	// aの素因数リストを取得
	var aPrimeList = getPrimeList(a);

	// bの素因数リストを取得
	var bPrimeList = getPrimeList(b);

	// 最小公倍数を保存する変数
	var lcm = 1;

	var i, j;

	// 共通の因数を保存する配列
	var list = new Array();

	// 共通の因数を保存し、掛け合わせる
	for (i = 0;i < aPrimeList.length;i++) {

		// bの因数リストを走査
		for (j = 0;j < bPrimeList.length;j++) {

			// aの因数がbにも含まれていたら共通因数の処理
			if (aPrimeList[i].num == bPrimeList[j].num) {

				// 因数の指数のうち大きな方を掛け合わせる
				if (aPrimeList[i].r > bPrimeList[j].r) {
					for (k = 0;k < aPrimeList[i].r;k++) {
						lcm *= aPrimeList[i].num;
					}
				} else {
					for (k = 0;k < bPrimeList[j].r;k++) {
						lcm *= aPrimeList[i].num;
					}
				}

				// 共通因数配列に追加
				list.push(aPrimeList[i].num);

			}
		}

	}

	// aの素因数分解リストから共通因数でない因数を抽出し掛け合わせる
	for (i = 0;i < aPrimeList.length;i++) {

		var flg = false;

		for (j = 0;j < list.length;j++) {
			if (aPrimeList[i].num == list[j]) {
				flg = true;
			}
		}

		if (!flg) {
			for (k = 0;k < aPrimeList[i].r;k++) {
				lcm *= aPrimeList[i].num;
			}
		}

	}

	// bの素因数分解リストから共通因数でない因数を抽出し掛け合わせる
	for (i = 0;i < bPrimeList.length;i++) {

		var flg = false;

		for (j = 0;j < list.length;j++) {
			if (bPrimeList[i].num == list[j]) {
				flg = true;
			}
		}

		if (!flg) {
			for (k = 0;k < bPrimeList[i].r;k++) {
				lcm *= bPrimeList[i].num;
			}
		}

	}

	return lcm;

}

さっそくテストしてみましょうか。

以下の入力欄に二つの整数(2以上)を入力し、「最小公倍数を求める」ボタンをクリックしてみてください。クリックすると、JavaScriptのイベントハンドラ内でgetLCM()が呼び出され、結果がダイアログで表示されます。

整数a: 整数b:

2と3、121と22などいくつか入れてみると、ちゃんと最小公倍数が求まっているようですね。