最大公約数とは
最大公約数って何？
そんなこともわからないの？仕方ないですね。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;取得した２つの数値の内、小さい方の数値をコピーしてその値をGとして、２つの数値を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億と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のアニメーションがわかりやすかったから
これを見るといいよ
以上
コメント