Greatest Common Divisor & Least Common Multiple

Greatest Common Divisor(GCD)

최대공약수를 구하는 법은 단순하게 확인하는 숫자보다 작은 모든 숫자를 확인하면서
두 숫자를 나눌 수 있는 수 중에 가장 큰것을 출력하는 것이다.

int gcd_naive(int a, int b) {
  int current_gcd = 1;
  for (int d = 2; d <= a && d <= b; d++) {
    if (a % d == 0 && b % d == 0) {
      if (d > current_gcd) {
        current_gcd = d;
      }
    }
  }
  return current_gcd;
}

이 방법은 모든 숫자를 확인해야 되기 때문에 항상 O(max(a, b)) 만큼 걸린다.
하지만 유클리드 호제법(Euclidean Algorithm)을 사용하면 더 빠르게 구할 수 있다.
유클리드 호제법 : 위키피디아 참고
유클리드 호제법을 사용하면 아래와 같다.

int gcd_fast(int a, int b) {
	int R;
	while ((a % b) > 0) {
		R = a % b;
		a = b;
		b = R;
	}
	return b;
}

위 방법보다 훨씬 빠르다.

Least Common Multiple(LCM)

최소공배수를 구하는 방법은 간단하다. 두 수의 곱은 GCD * LCM이다.
그러므로 두 수 a, b의 최소공배수는 (a * b)/GCD 이다.

long long lcm_fast(int a, int b) {
	long long lcm = (long long)a * b / (long long)gcd_fast(a, b);
	return lcm;
}