![[C#] 最小公倍数(LCM)を求めるアルゴリズムと実装](https://webbibouroku.com/wp-content/uploads/2016/07/csharp_log-710x410.png)
最小公倍数 – Least Common Multiple
最小公倍数とは、0ではない複数の整数の公倍数のうち最小の自然数をさします。
最小公倍数の求めかた
2つの正整数(a, b)の最小公倍数は、最大公約数が求めれば簡単に求まります。なぜなら最大公約数と最小公倍数には以下のような性質があるためです。
a * b = Gcd(a, b) * Lcm(a, b)2つの正整数(a, b)の積は、それらの最大公約数(GCD)と最小公倍数(LCM)の積に等しくなります。
2つの正整数の最大公約数は ユークリッドの互除法 を使えば求まります。
ユークリッドの互除法がわからない人は先に以下の記事を見てみることをお勧めします。
[C#] ユークリッドの互除法で最大公約数を求める方法 │ Web備忘録
例
具体的な例で正しいか確認してみます。24 と 10 について考えます。
- 最大公約数: 2
- 最小公倍数: 14
このとき 24*10 = 2*14 = 240 で最小公倍数と最大公約数の積が(a, b)の積に等しくなっています。
7 と 11 だと以下のようになります。
- 最大公約数: 1
- 最小公倍数: 77
このとき 7*11 = 1*77 = 77 で最小公倍数と最大公約数の積が(a, b)の積に等しくなっています。
証明
2つの正整数 a, b の最大公約数をg, 最小公倍数をl とする。2つの互いに素な整数 x, y を使うと
a = g*x
b = g*yと表せる。a, b の最小公倍数lは
l = g*x*yと表せるので
g*l = g*g*x*y = a*bとなる。
実装 C#
ユークリッドの互除法で最大公約数を求める関数を定義しておき、これを呼び出して使うようにします。
static long Lcm(long a, long b)
{
return a / Gcd(a, b) * b;
}
static long Gcd(long m, long n)
{
if (n == 0) return m;
return Gcd(n, m % n);
}Gcd(a, b)*Lcm(a, b) = a*b なので、あとは移行して Lcm(a, b) = a*b/Gcd(a, b) で求めることができます。
ただし、a * b / Gcd(a, b) と計算すると a*b でオーバーフローする可能性があるので、一応GCDでの割り算を先に行うようにしましょう。これで完成です。
Console.WriteLine(Lcm(72, 182)); // 6552
Console.WriteLine(Lcm(30, 42)); // 210
Console.WriteLine(Lcm(12, 18)); // 36
Console.WriteLine(Lcm(2, 10)); // 10こんな感じで使います。
以上。
