C言語で最大公約数を計算の方法

1年 ago
光, 明
1 minute

ユークリッドの互除算法を使って最大公約数を求めることもできます。その手順は以下のとおりです。

  1. 入力された２つの数字をそれぞれ変数aとbに格納します。
  2. 変数aとbの大きさを比較し、aがbより小さい場合は2つの変数の値を入れ替え、aを常にbより大きくするか等しくなるようにする。
  3. a に b の剰余を計算し、変数 c に格納します (c = a % b)。
  4. cが0であれば、bを最大公約数としてループを抜ける
  5. そうでなければ、b の値を a に代入し、c の値を b に代入して、次のループに進む。
  6. 出力変数の b の値が最大公約数です。

最大公約数を求めるC言語のサンプルコードを以下に示します。

#include <stdio.h>

int main() {
    int a, b, c;
    
    printf("请输入两个整数：");
    scanf("%d %d", &a, &b);
    
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    while ((c = a % b) != 0) {
        a = b;
        b = c;
    }
    
    printf("最大公约数为：%d\n", b);
    
    return 0;
}

プログラムを実行すると、2 つの整数を入力し、プログラムからその最大公約数が返されます。

bannerAds