[알고리즘] 최대공약수, 최소공배수

1. 유클리드 호제법

• 유클리드 호제법은 최초의 알고리즘으로 불리며 최대공약수(Greatest Common Divider)를 구하기 위한 알고리즘이다.
• 유클리드 호제법은 다음과 같다. (증명은 위키참조..)

  a >= b일 때,
  GCD(a, b) = GCD(b, r) (r : a % b)
  즉, (a, b)의 최대 공약수는 (b, a % b)의 최대 공약수와 같다는 것이다.
  이를 반복하면 a % b = 0일 때, b가 최대 공약수가 된다.

• 최대공약수를 구하면 최소공배수(Largest Common Multiple)은 쉽게 구할 수 있다.

  LCD(a, b) = a * b / GCD(a, b)

2. 구현

public void gcd (int a, int b) {
	while(b != 0) {
    	int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

public void lcm (int a, int b) {
	return a * b / gcd(a, b);
}