C++で最大公約数を計算する

2年 ago
海斗, 葵
1 minute

C++では、最大公約数をユーグリット法（辗転相除法）求めることができます。

以下に再帰を利用して最大公約数を求めるコード例を示します。

#include <iostream>
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
int a, b;
std::cout << "请输入两个数字：";
std::cin >> a >> b;
int result = gcd(a, b);
std::cout << "最大公约数为：" << result << std::endl;
return 0;
}

このコードでは、最大公約数を計算するためにgcd関数が使われます。再帰呼び出しの度に、bが0であれば、aは最大公約数です。そうでなければ、bが0になるまで、再帰的にgcd(b, a % b)が呼び出されます。

メイン関数では、ユーザーが2つの数字aとbを入力し、その後gcd関数を呼び出して最大公約数を計算し、結果を出力します。

また、最大公約数の計算は繰り返しを用いても実装できます

#include <iostream>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b;
std::cout << "请输入两个数字：";
std::cin >> a >> b;
int result = gcd(a, b);
std::cout << "最大公约数为：" << result << std::endl;
return 0;
}

上記のコードでは、gcd関数はループを用いて実装され、各ループでbの値がテンポラリ変数tempに格納され、その後aにbを代入し、bにはaをbで割った余りが代入されます。このループが終了すると、aは最大公約数になります。

bannerAds