C言語のwhileループで2つの数値の最大公約数（GCD）を求める方法

問題

C言語を使用して、任意の2つの整数の最大公約数（GCD：Greatest Common Divisor）を求めるプログラムを作成します。

解決策

まず、ユーザーにコンソールから任意の2つの数値を入力してもらいます。そして、入力された2つの数値に対して最大公約数を計算します。

2つの数値のGCD（最大公約数）とは、その2つの数値をどちらも余りなしで割り切ることができる最大の整数のことです。

2つの数値のGCDを求めるために使用するロジックは以下の通りです。

while(b!=0) // a/b の除算では b が 0 であってはならないため、b=0 かどうかをチェック
{
    rem = a % b;
    a = b;
    b = rem;
}
a を出力

このロジックは「ユークリッドの互除法」と呼ばれる古典的なアルゴリズムに基づいています。剰余演算（%）を繰り返し適用することで、効率よく最大公約数を導き出せます。

プログラム1：whileループを使用する方法

#include<stdio.h>
int main(){
    int a,b,rem;
    printf("enter any two numbers:");
    scanf("%d%d",&a,&b);
    while(b!=0) // 除算では b が 0 であってはならないためチェック
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    printf("GCD of two numbers is:%d\n",a);
    return 0;
}

実行結果

enter any two numbers:8 12
GCD of two numbers is:4

検算: 8  = 2 × 2 × 2
      12 = 2 × 2 × 3

2つの数値の最大公約数: 2 × 2 = 4

処理の流れの解説

入力例「8 12」の場合、処理は以下のように進みます。

• 1回目：rem = 8 % 12 = 8 → a=12、b=8
• 2回目：rem = 12 % 8 = 4 → a=8、b=4
• 3回目：rem = 8 % 4 = 0 → a=4、b=0
• b が 0 になった時点でループ終了 → 結果は 4

プログラム2：forループを使用する方法

次に、forループを使って2つの数値のGCDを求める別のアプローチを紹介します。この方法では、1から小さい方の数値まで順番に確認し、両方の数値を割り切る最大の値を記録していきます。

#include <stdio.h>
int main(){
    int num1, num2, i, GCD;
    printf("enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    for(i=1; i <= num1 && i <= num2; ++i){
        if(num1%i==0 && num2%i==0)
            GCD = i;
    }
    printf("GCD of two numbers is:%d", GCD);
    return 0;
}

実行結果

enter two numbers: 24 48
GCD of two numbers is:24

2つの方法の比較

• whileループ（ユークリッドの互除法）： 処理速度が非常に速く、大きな数値でも効率的に計算できます。
• forループ（全数探索）： ロジックが直感的で理解しやすい反面、数値が大きくなると計算量が増えて処理に時間がかかります。

実用的なプログラムでは、ユークリッドの互除法を用いた方法が推奨されます。