ユークリッドの互除法による最大公約数・最小公倍数
ユークリッドの互除法とは、2つの自然数の最大公約数を求める場合に 大きい方から小さい方を引き、さらに小さい方から引いてできた数を引く処理を繰り返して、 引く数と引かれる数が同じになったとき、それが最大公約数であるというものです。
これを使うと引き算だけで最大公約数を求めることができます。
具体的には次のようになります。
45 と 33 の 最大公約数を求める
45 - 33 = 12
33 - 12 = 21
21 - 12 = 9 ( 21 > 12 )
12 - 9 = 3
9 - 3 = 6
6 - 3 = 3 ( 6 > 3 )
3 - 3 = 0 <---- 3 が最大公約数
これを JavaScript で書くと次のようになります。
function gcd(a, b) {
return (a == b) ? a : gcd(Math.abs(a - b), (a > b) ? b : a);
}
ちなみに 上の例では何度も 3 を引いていますが 大きい方から小さい方を引くのではなく、 割った余りを求める方法だと もっと簡単になります。
次に最小公倍数ですが 最大公約数と最小公倍数には、下のような関係があります。
a × b = aとbの最大公約数 × aとbの最小公倍数
つまり最大公約数がわかれば最小公倍数は計算できるので 次のような JavaScript で最小公倍数が求められます。
function lcm(a, b) {
return a * b / gcd(a, b);
}
gcd() は、先ほど作った最大公約数を求める関数です。
JavaScript などのように 標準で最大公約数・最小公倍数を求める関数を持っていない言語を 使うときに これを知ってるとちょっと便利です。
