ユークリッドの互除法

ユークリッドの互除法とは、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₂の最大公約数である。

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

例

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);}

関連項目

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