【C言語】最大公約数をwhile文を使って求める方法

C言語を使って2つの整数の最大公約数を求める方法を学びたいですか？この記事では、古代ギリシャの数学者ユークリッドが考案した「ユークリッドの互除法」というシンプルで効率的なアルゴリズムを使って、最大公約数を求める方法を解説します。

さらに、C言語のwhile文を使ってこのアルゴリズムを実装する手順を具体的に説明します。

初心者の方でも理解しやすいように、サンプルコードとその実行結果も含めて詳しく説明しますので、ぜひ最後まで読んでみてください。

アルゴリズムの紹介

ユークリッドの互除法とは

ユークリッドの互除法は、古代ギリシャの数学者ユークリッドによって考案された、2つの整数の最大公約数(GCD: Greatest Common Divisor)を求めるための効率的なアルゴリズムです。

この方法は、2つの数の余りを繰り返し計算することで最大公約数を見つけることができます。

ユークリッドの互除法は、そのシンプルさと計算効率の高さから、現在でも広く使用されています。

ユークリッドの互除法の手順

ユークリッドの互除法の手順は以下の通りです：

1. 2つの整数 (a) と (b) を用意します(ここで (a > b) とします)。
2. (a) を (b) で割り、その余りを (r) とします。
3. (r) が0でない場合、(a) に (b) を、(b) に (r) を代入し、ステップ2に戻ります。
4. (r) が0になった時点で、(b) が最大公約数です。

この手順を繰り返すことで、最終的に最大公約数を求めることができます。

ユークリッドの互除法の例

具体的な例を見てみましょう。

例えば、48と18の最大公約数を求める場合を考えます。

1. (a = 48), (b = 18)
2. (48 /18 = 2) 余り (12) (ここで (r = 12))
3. (a = 18), (b = 12)
4. (18 / 12 = 1) 余り (6) (ここで (r = 6))
5. (a = 12), (b = 6)
6. (12 / 6 = 2) 余り (0) (ここで (r = 0))

この時点で余りが0になったので、最大公約数は (b = 6) です。

このように、ユークリッドの互除法を使うことで、簡単に最大公約数を求めることができます。

次のセクションでは、このアルゴリズムをC言語で実装する方法について詳しく説明します。

while文を使った最大公約数の計算

while文の基本構造

C言語におけるwhile文は、指定した条件が真(true)である間、繰り返し処理を行うための制御構造です。

基本的な構造は以下の通りです。

while (条件) {
    // 繰り返し実行する処理
}

条件が真である限り、whileブロック内の処理が繰り返し実行されます。

条件が偽(false)になると、whileループを抜けて次の処理に進みます。

while文を使った最大公約数の計算手順

ユークリッドの互除法をwhile文を使って実装する手順を以下に示します。

初期化

まず、2つの整数を入力として受け取り、それらを変数に格納します。

これらの変数を使って最大公約数を計算します。

#include <stdio.h>
int main() {
    int a, b;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &a, &b);

ループ条件

次に、while文の条件を設定します。

ユークリッドの互除法では、2つの数のうち小さい方が0になるまでループを続けます。

while (b != 0) {

ループ内の処理

ループ内では、2つの数のうち大きい方を小さい方で割った余りを計算し、その余りを次の計算に使います。

これを繰り返すことで、最終的に最大公約数が求められます。

int temp = b;
        b = a % b;
        a = temp;
    }

ループ終了後の処理

ループが終了した時点で、変数aには最大公約数が格納されています。

これを出力します。

printf("最大公約数は %d です\n", a);
    return 0;
}

結果の出力

以上の手順をまとめると、以下のような完全なプログラムになります。

#include <stdio.h>
int main() {
    int a, b;
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &a, &b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    printf("最大公約数は %d です\n", a);
    return 0;
}

このプログラムを実行すると、ユーザーが入力した2つの整数の最大公約数が計算され、出力されます。

例えば、24と36を入力した場合、結果は12となります。

2つの整数を入力してください: 24 36
最大公約数は 12 です

このように、while文を使ってユークリッドの互除法を実装することで、簡単に最大公約数を求めることができます。