ユークリッドの互除法

提供: MonoBook
ナビゲーションに移動 検索に移動

ユークリッドの互除法英語:euclidean algorithm)とは、2個の正の整数最大公約数を比較的高速に求めるアルゴリズムである。

実装例[編集 | ソースを編集]

C言語[編集 | ソースを編集]

C言語によるシンプルな実装。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b,a%b);
}

C言語による再帰を使わない実装。

int gcd(int a, int b) {
    if (a <= 0 || b <= 0) {
        return 0;
    }
    while (0 < b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

Haskellによる実装例[編集 | ソースを編集]

Haskellで書くとこんな感じである。

gcd a b = if b<=0 then a else gcd b (mod a b)

OCamlによる実装例[編集 | ソースを編集]

OCamlで書くとこんな感じである。

let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a mod b);;

F#による実装例[編集 | ソースを編集]

F#で書くとこんな感じである。 F#はOCamlから派生したプログラミング言語なのでほとんど違いはない。 違いは除算演算子が「mod」ではなく「%」なくらいである。

let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a % b);;

関連項目[編集 | ソースを編集]