Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

最大公約数・最小公倍数を求めるメソッド

ユークリッドの互除法を用いて、
二つの値の最大公約数および最小公倍数を求めるメソッド。

//最大公約数gcd
static int gcd (int a, int b) {
	int temp;
	while((temp = a%b)!=0) {
		a = b;
		b = temp;
	}
	return b;
}


//最小公倍数lcm
static int lcm (int a, int b) {
	int temp;
	long c = a;
	c *= b;
	while((temp = a%b)!=0) {
		a = b;
		b = temp;
	}
	return (int)(c/b);
}


最小公倍数がint型で桁あふれを起こす場合は、long型を使う。


追記:再帰を用いることでシンプルに書ける、処理速度はほぼ同じ?

static int gcd (int x,int y) {return y>0?gcd(y,x%y):x;}


こちらの解答を参考にさせていただきました
Submission #1450553 - AtCoder Grand Contest 018