ユークリッドの互除法とは

   最大公約数 (Greatest Common Divisor) は、複数の整数の公約数のうち最大のものをさします。ユークリッドの互除法は、2つの自然数の最大公約数を求める手法の一つです。紀元前300年頃には存在していたという、とても古くからあるアルゴリズムです。

   最大公約数(GCD) を求める方法で最初に思いつくのが素因数分解をすることです。しかし一般に、素因数分解は数が大きくなればなるほど、非常に難しい(時間がかかる)とされています。

   ユークリッドの互除法は最大公約数を求めるアルゴリズムですが、素因数分解は行わず、効率的に最大公約数を求めることができます。これは以下の式が成立することを利用します。

   GCD(a, b) = GCD(b, r)

   r は a/b の 余りを意味します。つまり、a と b の 最大公約数と b と r の最大公約数は等しくなるということです。

アルゴリズムの解説

詳しいアルゴリズムは以下の通りです。Wikipediaの内容の引用です。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
...
(問題) 1071 と 1029 の最大公約数を求める。
  • 1071 を 1029 で割った余りは 42
  • 1029 を 42 で割った余りは 21
  • 42 を 21 で割った余りは 0
よって、最大公約数は21である (wikipedia)

サンプルコード

C#

// 再帰関数でユークリッドの互除法
public static int GetGcd(int a, int b)
{
    return b != 0 ? GetGcd(b, a % 2) : a;
}

// ループでユークリッドの互除法
public static int GetGcd2(int a, int b)
{
    while (b != 0)
    {
        var r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Haskell

main = print $ getGcd 1071 1029 -- 21

-- 最大公約数を求める関数
getGcd :: Int -> Int -> Int
getGcd a 0 = a
getGcd a b
    | a `mod` b == 0 = b
    | otherwise = getGcd b $ a `mod` b