Edited at

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

More than 1 year has passed since last update.


最小公倍数を求める方法

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