2013年9月5日 (木) 13:06時点におけるimported>MikeCATによる版
ユークリッドの互除法とは、2個の正の整数の最大公約数を比較的高速に求めるアルゴリズムである。
実装例
シンプルな実装
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
再帰を使わない実装
int gcd(int a,int b) {
if(a<=0 || b<=0)return 0;
while(b>0) {
int t=a%b;
a=b;
b=t;
}
return a;
}
gcd a b = if b<=0 then a else gcd b (mod a b)
関連項目