유클리드 호제법 알고리즘: 최대공약수와 최소공배수

"유클리드 알고리즘" 원리.
-임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정해보겠습니다.
-a를 b로 나눈 나머지를 n 이라고 하면 (a%b = n)
-n이 0일때, b가 최대 공약수(GCD)입니다.
-만약 n이 0이 아니라면, a에 b값을 다시 넣고 n를 b에 대입 한 후 다시 위에 step2부터 반복하면 됩니다.

// 최대공약수 반복문 방식
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);
}