C#でGCD（最大公約数）とLCM（最小公倍数）を求めるプログラムの作成方法

GCD（最大公約数）とは？

GCD（Greatest Common Divisor：最大公約数）とは、複数の整数をすべて余りなく割り切ることができる正の整数のうち、最も大きなものを指します。たとえば、10と16の最大公約数は「2」です。

LCM（最小公倍数）とは？

LCM（Least Common Multiple：最小公倍数）とは、2つの整数のどちらによっても割り切れる整数のうち、最も小さいものを指します。たとえば、10と16の最小公倍数は「80」です。

GCDとLCMの間には、次のような重要な関係が成り立ちます。

LCM × GCD ＝ 2つの数の積

この性質を利用すると、まずユークリッドの互除法でGCDを求めてしまえば、LCMは「2つの数の積 ÷ GCD」という式で簡単に計算できます。

C#による実装例

以下は、C#で10と16のGCDおよびLCMを計算するサンプルプログラムです。GCDの計算には「ユークリッドの互除法」を採用しています。

using System;

namespace Demo {
   class Program {
      static void Main(string[] args) {

         int val1, val2, n1, n2, x;
         int resLCM, resGCD;
         val1 = 10;
         val2 = 16;

         // ユークリッドの互除法でGCDを求める
         n1 = val1;
         n2 = val2;
         while (n2 != 0) {
            x = n2;
            n2 = n1 % n2;
            n1 = x;
         }

         resGCD = n1;
         resLCM = (val1 * val2) / resGCD;

         Console.WriteLine($"{val1} と {val2} の LCM: {resLCM}");
         Console.WriteLine($"{val1} と {val2} の GCD: {resGCD}");
         Console.ReadKey();
      }
   }
}

実行結果

10 と 16 の LCM: 80
10 と 16 の GCD: 2

コードのポイント

ユークリッドの互除法： whileループの中で「n1をn2で割った余り」を繰り返し計算します。n2が0になった時点でのn1がGCDとなります。この手法は非常に効率的で、大きな数同士でも高速に最大公約数を求められます。

LCMの計算： 「val1 × val2 ÷ GCD」という公式で最小公倍数を求めています。なお、元のコードのように WriteLine("LCM: ", val1, val2, resLCM) と書いても値は表示されません。書式指定子や文字列補間（$"{変数名}"）を使う必要がある点に注意しましょう。

また、大きな数を扱う場合は掛け算によるオーバーフローを避けるため、(val1 / resGCD) * val2 の順に計算するのも有効です。