ユークリッドの互除法

ユークリッドの互除法とは、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;
}

Haskellによる実装

gcd a b = if b<=0 then a else gcd b (mod a b)

関連項目

• 最大公約数
• 最小公倍数