最大公約数を求める

最大公約数とは、二つの数に共通する約数（公約数）のうち最大のものです。たとえば、36と24の公約数は、1,2,3,4,6,12ですが、最大公約数はそれらの中で最大の12になります。

最大公約数を求めるアルゴリズム

この最大公約数を求めるアルゴリズムは、二つの数をそれぞれ因数分解し、その「共通部分」の積を計算するものになります。（素）因数分解は、ある数の「（素数の）約数」を求めることですから、その共通部分をすべて集めて乗算すれば、それが最大公約数になるわけですね。

今回は、因数分解のアルゴリズムを元に二つの自然数の最大公約数を求めてみましょう。

最大公約数を求めるには、二つの数を素因数分解し素数の積の形にして共通部分を集めます。ただし、今回は素因数分解をすることではなく最大公約数を求めることが目的なので、「二つの数の共通の素因数」を列挙し、その積から最大公約数を求めることにしました。

これは実質的には素因数分解と同じですが、素数で割って素因数を列挙する素因数分解の途中に「片方だけの素因数」が出てきたらその時点でやめることで無駄な計算を省く（片方だけの因数が最大公約数に含まれることはない）わけです。

具体的には、「二つの自然数a, b（a < b）がともに割り切れる（剰余が0）素数の公約数」を以下のアルゴリズムで乗算していきます。これは、ほぼ素因数分解と同じ手順ですね。

  1. 変数iに2を代入
  2. 変数gcmに1を代入
  3. a % i = 0かつb % i = 0の間、次の手順を繰り返す
  4. aとbをiで割り、gcmにiを掛ける。
  5. iを1増やして3に戻る（iがa以下の場合）

最大公約数を求めるプログラム（JavaScript）

今回は、このアルゴリズムをJavaScriptで書いてみました。特に最適化は行わず単純なコードで実装しています。

ただ、巨大な数が入ってくる可能性がある場合には素因数分解の計算量に注意が必要かもしれません。

// 自然数aとbの最大公約数を求める
function getGcm(a, b) {

	// a < bにする
	if (b > a) {

		c = a;

		a = b;
		b = c;


	}

	gcm = 1;

	// a,b共通の素因数を乗算
	for (i = 2;i <= a;i++) {

		// aとbがともにiで割り切れる間は割り続ける
		while (a % i == 0 && b % i == 0) {

			a /= i;
			b /= i;

			// 今回の除数を乗算
			gcm *= i;

			ex += "*" + i;

		}

	}

	// 結果を返す
	return gcm;

}
a= b=

aとbに適当な自然数（1以上の整数）を入力し、ボタンをクリックすると、最大公約数とその計算過程で乗算された素因数が表示されます。

最大公約数を求める処理は、整数処理の基本の一つなので自分で実装できるようにしておくと役に立つ場面もあるでしょう。