こんばんは。きわさです。
今回は最大公約数を求めるアルゴリズムについてです。
最大公約数
公約数とは、2つ以上の自然数について、いずれの約数にもなることができる数のことです。
最大公約数とは、公約数の中でも最大の数のことです。
では、例えば、
A = 2214523843
B = 1076234564
の2つの数の最大公約数は、と聞かれたらどう求めますか。
このようなプログラムで解くのは力技ですね。
1 2 3 4 5 6 7 8 | 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になったときの除数が最大公約数となります。
つまり次のように求められます。
1 2 3 4 5 6 7 8 9 | a = 2214523843;b = 1076234564;r = a % b;while(r != 0) { a = b; b = r; r = a % b;}printf("%d\n", b); |
今回わざと、2つの数をとても大きな数にし、最大公約数を小さい数にしているので、力技のほうで解いた場合は時間がかかります。
ユークリッドの互除法で解くと早いと感じられるかと思います。