C#:最小公倍数を求める

最小公倍数を求める方法

2つの正整数 a b があった時には、以下の関係が成り立ちます。

  a * b = gcd(a,b) * lcm(a,b) 

gcdは最大公約数、lcmwは最小公倍数を表します。
つまり、最大公約数を求められれば、最小公倍数を求めるのは簡単ですね。

例えば12と30という整数の時は、

 12 * 30 = (2 * 2 * 3) * (2 * 3 * 5) 
         = (2 * 3) * (2 * 2 * 3 * 5) 
         = 6 * 60 
         = 360

となり、6が最大公約数で、60が最小公倍数であることがわかります。

C#のコード

「最大公約数を求める」で示したGcdメソッドを、そのまま利用しています。

lcm.cs

using System;


namespace Gushwell.Etude {
    class Program {
        static void Main(string[] args) {
            var lcm = Lcm(28, 34);
            Console.WriteLine(lcm);
        }

        // 最小公倍数
        public static int Lcm(int a, int b) {
            return a * b / Gcd(a, b);
        }

        // ユークリッドの互除法 
        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でコードを公開しています。

---

ところで、このGcdとLcmなどメソッドをMath.Gcd(a,b)とか、Math.Lcm(a,b)のように書きたいけど、Mathクラスはすでに存在してるし、MathExクラスだとあまりにも安直だし...、でも他に思い浮かばないです。

---

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