Euclid!

ユークリッドの互除法 (Euclidean Algorithm) は記録に残る最古（紀元前300年頃）のアルゴリズムです。これを用いて2つ以上の自然数 (natural number) の最大公約数 (GCD) と最小公倍数 (LCM) を計算します。

[ 戻る ]

GCDとLCMの計算

項目	結果
GCD
LCM
互いに素

[ 戻る ]

使用方法

2以上9007199254740991 (=2⁵³−1) 以下の自然数を扱うことができます。
入力方式として、1つの入力ボックスに数値を1つ入力する[個別入力]、2つ以上の数値をカンマやスペース（連続可）で区切って入力する[一括入力]のいずれかが選択できます。
[個別入力]では自然数を5つまで入力できます。6つ以上入力するときは[一括入力]を選択してください。
[クリア]ボタンで入力値を消去できます。
[計算]ボタンで計算します。
算出する項目の意味は次の通りです。

最大公約数 (greatest common divisor) gcd(a,b,…)

2つ以上の自然数に共通な約数 (divisor) である公約数 (common divisor) の中で最大の自然数

最小公倍数 (least common multiple) lcm(a,b,…)

2つ以上の自然数に共通な倍数 (multiple) である公倍数 (common multiple) の中で最小の自然数

互いに素 (coprime)

2つ以上の自然数を共に割り切る正の整数が1のみであること。gcd(a,b,…)=1

[ 戻る ]

利用上の注意

Microsoft Edge、Internet Exploler 11、FireFox 45.0以降での動作を確認しています。
その他のブラウザでの動作は保証いたしません。
入力した自然数が1つの場合はその数自身を出力します。
計算結果が9007199254740991 (=2⁵³−1) より大きいときは指数表現の近似値になります。
計算結果が1.7976931348623157×10³⁰⁸ (≈2¹⁰²⁴) 以上のときは"Infinity"と表示します。
サポートは一切行いません。
気が向いたときに改良や修正をします。

[ 戻る ]

アルゴリズム

2つの自然数a, b(≠0)について、aをbで除したときの商 (quotient) をq、剰余 (remainder) をr (a=qb+r) とすると、gcd(a,b)=gcd(b,r)が成り立ちます。この関係を繰り返し適用し、r=0になったときのbが最大公約数gcd(a,b)になります。

var euclidean = function(a, b) {
/* Euclidean Algorithmによる最大公約数の計算 */
	var r;
	while (b !== 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return Math.abs(a);
};

アルゴリズム上では a≥b の必要がありますが、a<b であっても1周目のループで aとbが交換され、条件を満たすようになります。

最大公約数gcd(a,b)と最小公倍数lcm(a,b)の間にはgcd(a,b)×lcm(a,b)=a×bの関係があります。これを利用して最小公倍数はlcm(a,b)=a÷gcd(a,b)×bで求めることができます。このとき、先にgcd(a,b)で割るのは、a×bで桁あふれ (arithmetic overflow) が起こる可能性があるためです。

3つの自然数a, b, c(≠0)の最大公約数はgcd(a,b,c)=gcd(gcd(a,b),c)で求められます。即ち、aとbの最大公約数を求め、更にその結果とcの最大公約数で求めることで得ることができます。同様に最小公倍数もlcm(a,b,c)=lcm(lcm(a,b),c)で求めることができます。これらの操作を繰り返し適用することで、4つ以上の自然数の最大公約数と最小公倍数も得られます。

前述のeucldiean(a,b)関数を利用して、配列n[]に設定された2つ以上の自然数の最大公約数gcdと最小公倍数lcmを求めるコードを示します。途中gcdが1になった時点でgcdは1に決定されますので、以後のgcd計算を省略することができます。

/* 最大公約数gcdと最小公倍数lcmの計算 */
var imax = n.length;
var gcd = n[0];
var lcm = gcd;
var ni;
for (var i = 1; i < imax; i++) {
	ni = n[i];
	if (gcd > 1) gcd = euclidean(gcd, ni);
	lcm = lcm / euclidean(lcm, ni) * ni;
}

[ 戻る ]

参考文献

奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、平成6年9月25日初版第12刷（平成3年2月25日初版第1刷）

[ 戻る ]