『新･明解Ｃ言語入門編第２版』演習問題解答例８ー８

演習８ー８

問：二つの整数値xとyの最大公約数をユークリッドの互除法を用いて求める関数を制作せよ。

　int gcd(int x, int y)

// Ex0808.c

#include <stdio.h>

int gcd(int x, int y)
{
    int tmp;
    int max, min;
    
    if (x > y) {
        max = x;
        min = y;
    } else if (x < y) {
        max = y;
        min = x;
    } else {
        tmp = x;
        return tmp;
    }
    
    for (int i = 0; tmp > i; i) {
        tmp = max % min;
        max = min;
        min = tmp;
    }
    
    return max;
}

int main(void)
{
    int no1, no2;
    
    printf("整数Ａ：");
    scanf("%d", &no1);
    printf("整数Ｂ：");
    scanf("%d", &no2);
    
    printf("整数Ａ(%d)と整数Ｂ(%d)の最大公約数は %d です。\n", no1, no2, gcd(no1, no2));
    
    return 0;

}

コメント

　ユークリッドの互除法がわかれば大丈夫。ぐぐれば公式は出てきます。
　もっと最適化できるとは思う。

書籍情報