ユークリッドの互除法

ユークリッドの互除法とは、2つの自然数の最大公約数を求めるアルゴリズムである。

概要

最大公約数を求めたい2つの自然数をr₁, r₂ (r₁ ≧ r₂)とすると、以下のような手順で、r₁とr₂の最大公約数を求めることができる。

1. r₁ ÷ r₂ の余りr₃を求める。
2. r₂ ÷ r₃ の余りr₄を求める。
3. この手順を、r_n = 0になるまで繰り返す。
4. r_n-1がr₁とr₂の最大公約数である。

剰余の代わりに減算を用いる方法もあるが、両者の間に本質的な差異は何もない。

ユークリッドの互除法は最古のアルゴリズムとしても有名だが、優れたアルゴリズムと言われる所以は手数の少なさにある。アルゴリズムを終了するのに十分な手数は、r₂の桁数に比例するのである。具体的に言うと、r₂の10進桁数の5倍だけ行うまでに、結果がわかる。紀元前の時代にここまで優れたアルゴリズムが存在したことは注目に値する。

例

728と693の最大公約数を求める。

1. 728 ÷ 693 → 1 あまり 35
2. 693 ÷ 35 → 19 あまり 28
3. 35 ÷ 28 → 1 あまり 7
4. 28 ÷ 7 → 4 あまり 0

728と693の最大公約数は、7。

プログラミング言語での実装

Dによる実装

uint getGCD(uint a, uint b) {
 if(a < b)
 return getGCD(b, a);
 int r = a % b;
 if(r == 0)
 return b;
 return getGCD(b, r);
}

Cによる実装

int G(a,b){return a<b?G(b,a):(b>0?G(b,a%b):a);}

Lispによる実装

(define (gcd a b)
　　　　　　(if (= b 0)
               a
              (gcd b (remainder a b))))

関連項目

• アルゴリズム
• プログラミング関連用語の一覧