最大公約数とは

最大公約数って何?

そんなこともわからないの?仕方ないですね。wikipediaで調べてみましょう。
最大公約数(さいだいこうやくすう、英: greatest common divisor[注釈 1])とは、すべての公約数を約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。
wikipedia

うー、わからない。

例えば、20と16という数字が与えられた時、20は{1, 2, 4, 5, 10, 20}で割り切れる。
また、16は{1, 2, 4, 8, 16}で割り切れます。この数を、約数と言います。
20と16のそれぞれの約数で被っているのは{1, 2, 4}だね。これを公約数というんだ。
最大公約数とは、公約数のうち最大の数値のことを言うんだ。つまり、20と16の最大公約数は{4}ですね。

わかったぁ。
簡単だね。アルゴリズムが浮かんできたよ!!
ユークリッド互除法ってのはなんだかわかんないけど....

お!じゃ早速、思いついたアルゴリズムで求めてみよっか.
ユークリッド互除法は、その後に教えよう。
幼稚園生のアルゴリズム

じゃ、C++を用いて書くよ。

まずは、標準入力で2つの数値を取得するんだ
cin >> a >> c;

取得した2つの数値の内、小さい方の数値をコピーしてその値をGとして、2つの数値をG, G-1, G-2, ...., 1で割っていくんだ
1, 2, 3って小さい方の数値から割っていくよりも、大きい方の数値から見つける方が、最大公約数を見つけるのが速くなるって気づいたから、大きい方から割っていくよ。
if (a > c) {
for (int i = c; i >= 1; i--) {
// if (a % i == 0 && c % i == 0) return i;
}
} else if (a < c) {
for (int i = a; i >= 1; i--) {
// if (a % i == 0 && c % i == 0) return i;
}
}

最初に割り切れた数値が最大公約数になるよ
if (a > c) {
for (int i = c; i >= 1; i--) {
// if (a % i == 0 && c % i == 0) return i;
}
} else if (a < c) {
for (int i = a; i >= 1; i--) {
// if (a % i == 0 && c % i == 0) return i;
}
}

これで完成!と思いきや、引っ掛け!
取得した2つの値が同じ時、その数値自体が最大公約数になることを忘れないこと
else {
result = a;
}

よし! これで完成!
全部のコードを見せるよ
#include <iostream>
using namespace std;
int a, c;
int mmcm() {
int result = 0;
if (a > c) {
for (int i = c; i >= 1; i--) {
if (a % i == 0 && c % i == 0) return i;
}
} else if (a < c) {
for (int i = a; i >= 1; i--) {
if (a % i == 0 && c % i == 0) return i;
}
} else {
result = a;
}
return result;
}
int main() {
cin >> a >> c;
int result;
result = mmcm();
cout << result << endl;
return 0;
}

実行だ!
// input
30 6
// output
6

できたーー!

すごいですね!あの説明だけで....
正解です。
しかし、甘いですね。
そのアルゴリズムには欠点があります。

欠点ってなんだよ。

取得した2つの数値が小さい数値なら、欠点箇所は特にありません。
しかし、大きい数値ならどうでしょうか?
例えば、1垓1京1兆1億と1011垓921京112兆14億の時、計算量が多くなることは容易に想像できませんか?

た、確かに!

もしかして、そこでユークリッド互除法ですか?

正解! 感の良いガキは好きだよ
ユークリッド互除法で最大公約数を求める

ごちゃごちゃ説明しても意味わからなくなるので、いきなりコードを見せるよ
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y) {
int r;
// xとyの値を比較して、以降y < x であることを保障する
if (x < y) swap(x, y);
while (y > 0) {
r = x % y;
x = y;
y = r;
}
return x;
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
return 0;
}

とても簡単そう!

そうなんだ! 意外と簡単なんだ
実際の処理はこれだけ
while (y > 0) {
r = x % y;
x = y;
y = r;
}

じゃ、何をやっているのかを説明するよ。
この時点で、xが大きいことが明らかであることは前提
r = x % y xをyで割って、あまりをrとする
x = y xにyを代入
y = r yにrを代入する
yが0になるまでこれを繰り返す

そして、while文を抜けたときのxの値が最大公約数になるんだ

すごい! わかった
けどなんで、最大公約数になるの??

wikipediaのアニメーションがわかりやすかったから
これを見るといいよ
以上
コメント