最大公約数・最小公倍数を求めるメソッド
ユークリッドの互除法を用いて、
二つの値の最大公約数および最小公倍数を求めるメソッド。
//最大公約数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