アルパカログ

この記事ではJavaScript/TypeScriptで最大公約数と最小公倍数を求める方法を説明します。

最初に、最大公約数はユークリッドの互除法によって求めることができます。

• ユークリッドの互除法

ユークリッドの互除法とは、まず除算によって剰余（余り）得て、次に除数（割る数）を得た剰余で割る、そこで得た剰余でまた除数を割る……という手順を繰り返し、剰余が0になったときの除数が最大公約数として得られます。

JavaScriptで再帰関数を使って表すと下記のようになります。

const gcd = (a, b) => {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
};

最小公倍数は、ユークリッドの互除法で得られた最大公約数に加え、二つの整数X, Yの積とその最大公約数および最小公倍数の積は等しくなるという関係を利用して求めることができます。

JavaScriptでは、前述の最大公約数を求める関数を使って下記のように表すことができます。

const lcm = (a, b) => a * b / gcd(a, b);

ちなみに、英語では最大公約数はGreatest Common Divisor（GCD）、最小公倍数はLeast Common Multiple（LCM）です。

以上です。この記事ではJavaScript/TypeScriptで最大公約数と最小公倍数を求める方法を説明しました。