C#:最大公約数を求める （ユークリッドの互除法）

２つの整数の公約数のうち最大のもの（最大公約数）を求める方法として有名なのが「ユークリッドの互除法」です。このユークリッドの互除法を用い最大公約数を求めるメソッドをC#で書いてみました。

ユークリッドの互除法については、Wikipediaのこちらのページを参照してください

ループバージョン

gcd.cs

 class Program {
     static void Main(string[] args) {
         Console.WriteLine(Gcd(0, 8));
         Console.WriteLine(Gcd(12, 8));
         Console.WriteLine(Gcd(3400, 6596));
         Console.WriteLine(Gcd(12707, 12319));
     }
     // ユークリッドの互除法 
     public static int Gcd(int a, int b) {
         if (a < b)
             // 引数を入替えて自分を呼び出す
             return Gcd(b, a);
         while (b != 0) {
             var remainder = a % b;
             a = b;
             b = remainder;
         }
         return a;
     }
 }

GitHubでコードを公開しています。

再帰バージョン

a を bで割った時の余りを r とすると、

  b = 0 の時　-> gcd(a,b) = a
  b > 0 の時　-> gcd(a,b) = gcd(b,r)

と表せるので、再帰を使って書くことができます。

そのコードも載せておきます。

gcdRecursive.cs

 public static int Gcd(int a, int b) {
     return a > b ? GcdRecursive(a, b) : GcdRecursive(b, a);
 }
 
 private static int GcdRecursive(int a, int b) {
     return b == 0 ? a : GcdRecursive(b, a % b);
 }

再帰処理書く時、いつも思うのですが、メドッドの中でメソッド定義が出来れば便利なのにと思いますね。C#7.0期待しています。

ところで、C#6.0でも、以下のようにラムダ式使って、ひとつのメソッドで済ますこともできます。

gcdRecursive2.cs

public static int Gcd(int a, int b) {
    Func<int, int, int> gcd = null;
    gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
    return a > b ? gcd(a, b) : gcd(b, a);
}

GitHubでコードを公開しています。

ラムダ式と1文字変数と条件演算子が組み合わさって、呪文のようなコードになっちゃいましたが、短いメソッドなので許してください(笑)

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。