[Algorithm] 유클리드 호제법 (Euclidean)

유클리드 호제법을 이용해 최대공약수와 최소공배수를 구하는 기본 알고리즘이다

 

1. 큰 숫자를 작은 숫자로 mod연산
2. 작은 숫자를 1.의 결과와 mod연산
3. mod연산 결과가 0이 나올때 까지 2.과정을 반복
4. mod연산 결과가 0이 나왔을 때, 나누는 수가 두 수의 [최대공약수]
5. 두 수를 곱한 수를 최대공약수로 나누면 [최소공배수]

// 최대공약수: Greatest Common Division
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

// 최소공배수: Least Common Multiple
int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}