Help us understand the problem. What is going on with this article?

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で公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした