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

最大公約数(Greatest Common Divisor)を計算するためのアルゴリズムです。アルゴリズムの内容は、説明よりコードを見たほうが早いかもしれません。それほど単純で美しいアルゴリズムなのです。

#include <stdio.h>
 
int gcd(int, int);
 
// メイン
int main(void) {
  const int m = 27;
  const int n = 18;
  
  printf("%d と %d の最大公約数は %d です。\n", m, n, gcd(m, n));

  return 0;
}
 
// ユークリッドの互除法により、引数 m, n の最大公約数を求める。
int gcd(int m, int n) {
  if (m < n) return gcd(n, m);
 
  if (n == 0) return m;

  return gcd(n, (m % n));
}

実行結果

27 と 18 の最大公約数は 9 です。

解説

ユークリッドの互除法を自然言語で書くとこんな感じです。

1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、m を出力してアルゴリズムを終了する。
3. n を 新たな m とし、m を n で割った余りを新たに n として 2 に戻る。

上記のコードも、そのまんま3行になっています。大変分かりやすいですね。小学校の頃、分数を約分するときに考えていたことを思い出してみると分かりやすいと思います。もう少し簡単に説明しましょう。

自然数 m, n(m ≧ n) を割った剰余を r とすると、m と n との最大公約数は n と r の最大公約数と等しくなります。そのため、n を r で割った剰余、序数 r をその剰余で割った剰余…と剰余が 0 になるまで互い違いに計算を繰り返すことから “互除法” と呼ばれるわけです。

もっと簡潔に言えば、自然数 m, n(m ≧ n)に対して、m を n で割った余りを r とすると、gcd(m, n) = gcd(n, r) が成立し、これを繰り返し適用することで m と n の最大公約数が求まるということです。

多くの学生の心をへし折ってきた素因数分解によって最大公約数を求めることより、ユークリッドの互除法が好まれる理由は大きな値の最大公約数を求めることを想像すると、割り算のほうが圧倒的に計算量が少ないことが分かるでしょう。

最悪なケースは、隣り合うフィボナッチ数になっている場合です。何故なら計算量を増やすためには、余りが最も減りにくいパターンの自然数を与える必要があります。つまり、余りが(n – 1)になれば良い訳ですから 最小の m は(2n – 1) になります。

これを逆から見ていくと、(1, 1), (2, 3), (3, 5), (5, 8) と隣り合うフィボナッチ数になります。