[코딩테스트/Javascript] 최대공약수(GCD)/최소공배수(LCM)와 유클리드 호제법

코테 빈출 개념인 최대공약수와 최소공배수를 계산하는 방법을 정리해 보겠습니다

 

최대공약수 = Greatest Common Divisor = GCD

최소공배수 = Least Common Multiple = LCM

 

수학 공식

소인수분해를 통해 계산

공배수	최소공배수의 배수
공약수	최대공약수의 약수
최대공약수	공통 소인수, 지수는 최소
최소공배수	모든 소인수, 지수는 최대

 

12 = 2² × 3
18 = 2 × 3²

 

GCD = 2 × 3 = 6

LCM = 2² × 3² = 36

 

최대공약수

약수 이용

→ 두 수의 공약수 중 최대 값을 구한다

 

1. i를 1부터 두 수(n, m) 중 더 작은 값(min)의 제곱근까지 증가시키며 순회

공약수는 min을 넘을 수 없다. 예를 들어 n = 12, m = 15일 경우 두 수의 공약수는 12를 넘길 수 없기 때문에 1~12까지만 확인

 

제곱근까지만 확인하면 되는 이유는 아래 참고 ↓

[코딩테스트/Javascript] 약수와 약수 찾기

 

2. i가 min의 약수인지 확인

 

3. pair = min / i를 구한 뒤, 이 값이 max의 약수인지 확인

min = i * pair 의 형태에서 i는 1부터 증가하고 pair은 min부터 감소하는 형태이기 때문에 항상 i <= pair가 보장되며

만약 큰 수인 pair가 max의 약수라면 이후 반복문에서는 더 큰 공약수를 찾을 수 없으므로 반복문을 조기 종료

min = 36 예시

 

4. i 가 max의 약수인지 확인

이 경우는 i가 공약수이지만, 이후 반복문에서 더 큰 공약수를 발견할 수 있기 때문에 우선 저장 후 순회를 계속한다

 

  const gcd = (a, b) => {
    let min = Math.min(a, b);
    let max = Math.max(a, b);
    let cd = 0;

    for (let i = 1; i * i <= min; i++) {
      if (min % i === 0) {
        let pair = min / i;
        if (max % pair === 0) {
          cd = pair;
          break;
        } else if (max % i === 0) cd = i;
      }
    }

    return cd;
  };

 

 

유클리드 호제법

→ 두 수의 최대공약수는 큰 수를 작은 수로 나눈 나머지와 작은 수의 최대공약수와 같다

어떤 수 min과 max에서 max = min * q + r 이라고 할 때 max와 min의 최대공약수는 min과 r의 최대공약수와 같다

 

1. 두 수에서 큰 값(max)과 작은 값(min)을 찾아서 [max, min] = [min, max % min] 계산을 나머지가 0이 될 때까지 반복

  const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
  };

 

예를 들어 gcd(48, 18) 일 때

[48, 18] = [18, 12] = [12, 6] = [6, 0] 이므로 최대공약수는 6이 된다

 

최소공배수

최소공배수는 두 수를 곱했을 때 중복된 공통 소인수(최대공약수)를 제거한 값과 같다

LCM = (a × b) / GCD

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}