ユークリッドの互除法で最大公約数を求める

こんばんは。きわさです。

今回は最大公約数を求めるアルゴリズムについてです。

最大公約数

公約数とは、2つ以上の自然数について、いずれの約数にもなることができる数のことです。
最大公約数とは、公約数の中でも最大の数のことです。

では、例えば、
A = 2214523843
B = 1076234564
の2つの数の最大公約数は、と聞かれたらどう求めますか。

このようなプログラムで解くのは力技ですね。

a = 2214523843;
b = 1076234564;
for(i = a>b?b:a; i > 0; i--) {
    if((a%i == 0) && (b%i == 0)) {
        printf("%d\n", i);
        break;
    }
}

これでも最終的には解けますが、少し時間がかかります。
そこで、ユークリッドの互除法を使ってみます。

ユークリッドの互除法

ユークリッドの互除法は2つの自然数の最大公約数を求める方法の一つです。

2つの自然数a, b(a >= b)について、aのbによる剰余をrとすると、aとbとの最大公約数はbとrとの最大公約数に等しい
という性質を使います。
bのrによる剰余、rのその剰余による剰余、と繰り返し最後に剰余が0になったときの除数が最大公約数となります。

つまり次のように求められます。

a = 2214523843;
b = 1076234564;
r = a % b;
while(r != 0) {
    a = b;
    b = r;
    r = a % b;
}
printf("%d\n", b);

今回わざと、2つの数をとても大きな数にし、最大公約数を小さい数にしているので、力技のほうで解いた場合は時間がかかります。
ユークリッドの互除法で解くと早いと感じられるかと思います。