本記事では入力した2個の整数から最大約数を求めるプログラムを2パターン紹介します。
for文を使ったシンプルな実装
最大公約数を求める一番シンプルな実装はfor文を使って入力された数値の両方で割ることができる、値を見つける方法です。
入力値のうちの大きい自然数をa、小さい自然数をbとします。
2~bまでの数でaとbの両方で割れる最大の数を見つけるプログラムを書けば最大公約数を求めることができます。
サンプルコードは以下の通りです。
#include <iostream>
using namespace std;
int main(void){
int a,b;
cin >> a >> b;
int tmp = 0;
if (a < b){
tmp = a;
}
else{
tmp = b;
}
int gcf = 1;
for (int i= 2; i<=tmp; ++i){
if ((a % i == 0) && (b % i == 0)){
gcf = i;
}
}
cout << gcf << endl;
return 0;
}
ユークリッド互除法を使う効率の良い実装
入力値のうちの大きい自然数をa、小さい自然数をbとします。
ユークリッド互除法とは、aをbで割った余りをrとすると、aとbの最大公約数はbとrの最大公約数に等しくなるという法則です。
例えば390と273という数値が入力されたとします。
390 ÷ 270 = 1 あまり 117
これをユークリッド互除法の法則に当てはめると
「390と270の最大公約数 = 270と117の最大公約数」ということになります。
これを割り切れるまで繰り返していくと、割り切れる一つ前の余りの値が最大公約数になります。
ユークリッド互除法を使って最大公約数を求めるサンプルコードは以下のとおりになります。
#include <iostream>
using namespace std;
int main(void){
int a,b,tmp;
cin >> a >> b;
if (a < b){
tmp = b;
b = a;
a = tmp;
}
while(b != 0){
tmp = b;
b = a % b;
a = tmp;
}
cout << a << endl;
}
コードの長さもループを使って闇雲に求めた方法より少なく、シンプルです。
今回はループを使ってユークリッド互除法を使って最大公約数を求めるプログラムを書きましたが、再起関数を使用することでよりすっきりした実装になります。
最後に
本記事をとおして、ユークリッド互除法を使うことで効率よく最大公約数を求めることができることが分かりましたか。
単純に小さい数から割っていって、最大公約数を求める方法もいいのですが、計算量やコード量を意識してより効率のよい実装を行いましょう。