ユークリッドの互除法

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

概要

最大公約数を求めたい2つの整数を m、n （どちらか一方が0以上の整数、もう一方が正の整数）とすると、以下のような手順で、m と n の最大公約数を求めることができる。

1. n = 0の場合、m を最大公約数として終了する。n ≠ 0（すなわち n > 0）の場合、2.へ進む。
2. m ÷ n の剰余を r とする。
3. m に n、n に r を代入する。
4. 1.へ戻る。

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

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

例

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

	m	n	r
(1)	728	693	35
(2)	693	35	28
(3)	35	28	7
(4)	28	7	0
(5)	7	0	-

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

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

ここではC言語での実装例を記載する。他のプログラミング言語においても、ループ処理、再帰処理等が実装可能であれば大体同じようにして実装出来る。なお、引数 m、n については前提条件（どちらか一方が0以上の整数、もう一方が正の整数）を必ず満たしているものとする。

ループ処理による実装

int getGCD(int m, int n) {
    int r;
    while (n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

再帰処理による実装

int getGCD(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return getGCD(n, m % n);
    }
}

再帰処理及び三項演算子による実装

int getGCD(int m, int n) {
    return n == 0 ? m : getGCD(n, m % n);
}

関連動画

高校数学の範囲での証明方法である。

関連項目

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