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

この記事では、C言語を使って最大公約数を求める方法を解説します。

最大公約数の求め方

最大公約数(Greatest Common Divisor, GCD)は、2つ以上の整数の中で共通の約数のうち最大のものを求める方法です。

C言語では、ユークリッドの互除法やwhile文を使った方法などがあります。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数の最大公約数を求めるためのアルゴリズムです。

以下の手順で最大公約数を求めることができます。

1. 2つの整数をaとbとします。
2. aをbで割った余りをrとします。
3. rが0でない場合、bをaとし、rをbとして2に戻ります。
4. rが0の場合、bが最大公約数となります。

ユークリッドの互除法は、再帰的に計算することもできますが、ここではwhile文を使った方法を解説します。

while文を使った最大公約数の求め方

以下のサンプルコードは、while文を使って2つの整数の最大公約数を求める方法を示しています。

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

このサンプルコードでは、ユーザーに2つの整数を入力してもらい、while文を使って最大公約数を求めています。

aとbの値が等しくなるまで、大きい方の値から小さい方の値を引いていきます。

最終的にa(またはb)の値が最大公約数となります。

以上が、C言語で最大公約数を求める方法の解説です。

ユークリッドの互除法やwhile文を使った方法を使って、効率的に最大公約数を求めることができます。