ユークリッド互除法

質問

ユークリッド互除法を使用して最大公約数を求めるプログラムを、C言語で書いてみました。

#include <stdio.h>

main()
{
int a, b, t;

scanf("%d %d", &a, &b);

if(a<b){
t=a;
a=b;
b=t;
}

while(b != 0){
t = a % b;
a = b;
b = t;
}
printf("GCD = %d\n", a);
return 0;
}

これを、もっと簡略化できるらしいのですが、これ以上できることはありますか？

どう考えてもわかりません

回答No.5

D-Matsu

b > aでループインした場合、初回はswapと等価の動作をするのでループ前にわざわざ入れ替える必要ナシ、ってことではないですか。
それよりa, bの自然数判定がないのが気にかかりますが。

回答No.4

Tacosan

もっとヒント: なんで a ≧ b じゃないと都合が悪いの?

回答No.3

chie65536

aがbより小さい場合に、aとbを入れ替える処理
t=a;
a=b;
b=t;
の３行と、互除法のループの処理
t = a % b;
a = b;
b = t;
を見比べてみよう。

違うのは、１行目が
t=a;
か
t = a % b;
かの違いしかない。２、３行目は同じだ。

って事は、１行目を工夫すれば、共通の処理に簡略化できそうだ。ループの中に大小比較が入るので、速度が落ちると言う欠点はあるが。

#include <stdio.h>

main()
{
int a, b, t;

scanf("%d %d", &a, &b);

while(b){
t = (a < b) ? a : a % b;
a = b;
b = t;
}
printf("GCD = %d\n", a);
return 0;
}

回答No.2

psychesine

自分が他に見たソースと同じですよ。

if文が入る理由は、ユークリッド互除法の条件で a が b 以上である事が
条件だからでは？

回答No.1

Tacosan

if 文を入れた理由は?