Gcm Lcm の説明

GCM(最大公約数)とLCM(最小公倍数)の説明です。

前田稔(Maeda Minoru)の超初心者のプログラム入門

Gcm Lcm

私のホームページでは、プログラムの財材として Gcm Lcm を良く使っています。
その都度 GCM(最大公約数)と LCM(最小公倍数)を説明するのは無駄なので、ここにまとめて説明します。
LCM(最小公倍数)とは、分数計算をするときの分母になる値です。
例えば 1/2 + 1/3 を計算する時 3/6 + 2/6 = 5/6 が答えです。
このとき分母となる 6 が最小公倍数です。

最小公倍数を求めるとき、先に最大公約数を求めます。
最大公約数とは、分母を割り切ることが出来る最も大きな値です。
例えば 1/24 + 1/32 のとき、24 と 32 を割り切る 8 が最大公約数です。
最大公約数が求まれば、最小公倍数は次の式で計算出来ます。
最小公倍数 = data1 * data2 / gcm(data1,data2)
1/24 + 1/32 のときは 24*32/8 = 96 が最小公倍数です。

ユークリッドの互除法

GCM(最大公約数)を求める方法として、有名な数学者ユークリッドが考案したユークリッド互除法があります。
今 data1 と data2 の GCM を求めることを考えます。
% は余りを求める演算子です。

  1. data1 > data2 のとき data1 % data2 == 0 のとき data2 が GCM である
    0 でない時、余りを data1 の値とする
  2. data2 > data1 のとき data2 % data1 == 0 のとき data1 が GCM である
    0 でない時、余りを data2 の値とする
  3. ①②を繰り返す

例として data1=12, data2=32 として計算してみましょう。
  1. 32 % 12 = 8 であり data2 の値を 8 とする
  2. 12 % 8 = 4 であり data1 の値を 4 とする
  3. 8 % 4 = 0 となり GCM は 4 である
  4. 従って最小公倍数は 12*32/4 = 96 となる

Gcm のプログラム

余りを求める演算子(%)が使えない言語があり、数学ライブラリを組み込まなければならないことがあります。
そこで私のプログラムでは % を使わずに「減算で対応」しています。

  1. data1 と data2 が等しいとき data1(または data2) が最大公約数です。
  2. data1 が data2 より大きいとき data1 -= data2 を計算して ① に戻ります。
  3. data2 が data1 より大きいとき data2 -= data1 を計算して ① に戻ります。

C++ でコーディングすると次のようになります。
    int gcm(int v1, int v2)
    {
        int w1 = v1;
        int w2 = v2;
        while(w1 != w2)
        {   if (w1 > w2)    w1 -= w2;
            else            w2 -= w1;
        }
        return w1;
    }