ユークリッドアーク除算アルゴリズム:最大公倍数と最小公倍数

「ユークリッドアルゴリズム」の原理.
−任意の2つの自然数a,bが与えられた場合.いずれかの大きな値がaであると仮定します.
-aをbで割った残りの部分をn(a%b=n)と呼ぶ場合
−nが0の場合、bは最大公約数(GCD)である.
-nが0でない場合は、aにb値を再入力し、nをbに代入し、上記の手順2を繰り返すだけでよい.

// 최대공약수 반복문 방식
int gcd(int a, int b) {
	
	while(b != 0) {
		int r = a % b;	// 나머지를 구해준다.
        
		// GCD(a, b) = GCD(b, r)이므로 변환한다.
		a = b;		
		b = r;
	}
	return a;
}
 
// 최대공약수 재귀 방식
int gcd(int a, int b) {
	if(b == 0) return a;
	// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
	return gcd(b, a % b);
}
 
// 최소공배수 : Least Common mulitple
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}