C++での最大公約数（HCF）の見つけ方

2024-02-29 08:25 C++ 最大公約数 HCF

ユークリッドの互除法を使用する方法: ユークリッドの互除法は、2つの整数の最大公約数を見つける最も一般的な方法です。アルゴリズムは次のようになります。
```
int gcd(int a, int b) {
   if (b == 0) {
       return a;
   }
   return gcd(b, a % b);
}
```
この関数は再帰的に呼び出され、2つの整数の最大公約数を返します。

例:
```
int a = 24;
int b = 36;
int result = gcd(a, b);
// resultは12になります
```
ループを使用する方法: ユークリッドの互除法をループで実装することもできます。以下はそのコード例です。
```
int gcd(int a, int b) {
   while (b != 0) {
       int temp = b;
       b = a % b;
       a = temp;
   }
   return a;
}
```
この方法では、ループを使用して最大公約数を見つけます。

例:
```
int a = 24;
int b = 36;
int result = gcd(a, b);
// resultは12になります
```
標準ライブラリを使用する方法: C++の標準ライブラリには、最大公約数を見つけるための関数も用意されています。
```
#include <numeric>

int a = 24;
int b = 36;
int result = std::gcd(a, b);
// resultは12になります
```
<numeric>ヘッダをインクルードし、std::gcd関数を使用して最大公約数を見つけることができます。

これらの方法のいずれかを使用して、C++で最大公約数を見つけることができます。必要に応じて、上記のコード例をカスタマイズして使用してください。