最大公約数を求める

最大公約数とは、二つの数に共通する約数（公約数）のうち最大のものです。たとえば、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で書いてみました。

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