アルゴリズム問題の解法としての最大公約数とユークリッドの互除法

アルゴリズム問題によく登場する「最大公約数」について考えてみましょう。数式を重視しながら、具体的なプログラムコードよりも、考え方に焦点を当てます。

最大公約数の定義とは？

最大公約数とは、2つ以上の自然数に対して、それぞれの約数から共通する最大の数のことを指します。

最大公約数の求め方

最大公約数を求める方法は2つあります。

1. 共通の数で割っていき、割れなくなったところで計算を終了します。ここまでの割った値を掛けていくと、最大公約数が得られます。
2. ユークリッドの互除法を使用します（プログラム向きな方法）。

解法1: 共通の数で割っていく方法

共通の数（例えば2や3など）で割っていき、これ以上共通の数で割れなくなった段階で計算を終了します。この方法は非常にシンプルですが、プログラムを作成する際に共通な数を探す作業と割り算の両方が必要です。

解法2: ユークリッドの互除法

まず、2つの数の大きい方を小さい方で割ります。次に、割った数を先程の割り算の余りで割ります。これを繰り返し行い、あまりが0になったところで計算を終了し、その時の割った数が最大公約数となります。

ユークリッドの互除法では、割り算と式の組み替えの2つの処理が必要ですが、コンピュータにとってはどちらも簡単なため、プログラムで実装する際に有効です。

注意点とまとめ

ユークリッドの互除法は2つの数に対して有効であり、3つ以上の数の最大公約数を求める場合は解法1を使用する必要があります。最大公約数の求め方を理解したら、プログラムを通じて実際に実装してみましょう。

以下に、C++による最大公約数の計算例を示します。

#include <iostream>

using namespace std;

int main() {
    unsigned int a, b, amari;
    cout << "1つ目の数を入力してください: ";
    cin >> a;
    cout << "2つ目の数を入力してください: ";
    cin >> b;

    if (a < b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    while (1) {
        amari = a % b;
        if (amari == 0) break;
        else {
            a = b;
            b = amari;
        }
    }

    cout << "最大公約数は: " << b << endl;

    return 0;
}

再帰関数バージョン（かしこい）

// 与えられた2つの正の整数の最大公約数を出力（再帰関数）

#include <iostream>

using namespace std;

unsigned int gcd(const unsigned int a, const unsigned int b){
        return (b == 0) ? a : gcd(b, a % b);
}

int main(){
    unsigned int a, b;
    cout << "Input first number: ";
    cin >> a;
    cout << "Input second number: ";
    cin >> b;
    cout << gcd(a, b) << endl;
}