【C#】最大公約数・最小公倍数を求める

はじめに

今回は二つの整数の最大公約数を求めるプログラムについてやっていきたいと思います。

最大公約数とは共通の約数のうち最大のもののことを指します。

例えば12と18の最大公約数は6となります。

早速やっていきましょう。

求め方

最大公約数はユークリッドの互除法を用いることで求められます。

1. m を n で割り、その余りが r
2. r が 0 なら n が最大公約数
3. r != 0なら、m = n，n = r として 1 の手順に戻る

プログラム

最大公約数gcd(m, n)の例のひとつを作ってみました。

/// <summary>
/// 最大公約数
/// </summary>
public static long Gcd(long m, long n)
{
    // m >= n にする
    if(m < n)
    {
        var tmp = m;
        m = n;
        n = tmp;
    }

    while(true)
    {
        var r = m % n;
        if (r == 0) return n;
        m = n;
        n = r;
    }
 }

最小公倍数を求める

最小公倍数は共通な倍数（公倍数）のうち最小のものです。

例えば2と3の最小公倍数は6となります。

最大公約数gcd(m, n)と最小公倍数lcm(m, n)には以下の関係があるみたいです。

gcd(m, n) ・ lcm(m, n) = m・n 

これをプログラムにするとこんな感じになります。

/// <summary>
/// 最小公倍数
/// </summary>
public static long Lcm(long m, long n)
{
    var gcd = Gcd(m, n);
    return (m * n) / gcd;
}

さいごに

実際にプログラムにしてみるとシンプルでしたね。

是非うまく活用してみてください！