유클리드 호제법

최대공약수(GCD), 최소공약수(LCM)을 유클리드 호제법으로 구하기

1. 유클리드 호제법으로 GCD 구하기

원리:

1. 두 수 a와 b가 있습니다. (a, b 크기는 상관없음)
2. a를 b로 나눈 나머지 r을 구합니다.
3. a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.
4. r이 0이 될 때, 그때의 b 값이 최대공약수입니다. (이것이 재귀의 베이스 케이스(Base Case)가 됩니다.)

public int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

2. GCD로 최소공배수(LCM) 구하기

두 수 a, b의 최소공배수 = (a * b) / GCD(a, b)

public int lcm(int a, int b) {
  // 0으로 나누는 것을 방지
  if (a == 0 || b == 0) {
    return 0; 
  }

  int gcdValue = gcd(a, b); // 재귀로 GCD 호출

  return (a / gcdValue) * b; // a * b의 int overflow 대비 연산 순서 변경
}