Edited at

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

More than 1 year has passed since last update.

2つの整数の公約数のうち最大のもの(最大公約数)を求める方法として有名なのが「ユークリッドの互除法」です。このユークリッドの互除法を用い最大公約数を求めるメソッドを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で公開したものを加筆・修正したものです。