[JS] 최대공약수(GCD), 최소공배수(LCM) 구하기

1. 루프 돌리기

1. 최대공약수

최대공약수는 두 수 A, B의 공통 약수들 중 가장 큰 정수이다.

가장 직관적인 방법은 min(A, B)부터 1까지 루프를 돌려 각 수를 나누어보는 방법이다.

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

  for(let i = max; i >= 1; i--){
    if(a % i === 0 && b % i === 0){
      gcd = i;
      break;
    }
  }

  return gcd;
}

2. 최소공배수

최소공배수는 A, B의 공통인 배수들 중 가장 작은 정수이다.

가장 직관적인 방법은 max(A, B)부터 시작하는 루프를 돌려 각 수들로 나누어보는 방법이다.

const getLCM = (a, b) =>{
  const min = Math.max(a, b);
  let lcm = min;
   
  while(true){
    if((lcm % a == 0) && (lcm % b == 0)){
      break;
    }
    lcm++;
  }
  return lcm
}

하지만 A, B 숫자가 너무 크거나 비교할 숫자가 두개가 아니라 여러개일 경우 문제가 된다.

 

 

2. 유클리드 호제법

두 수 A, B의 최대공약수(GCD)와 최소공배수(LCM)의 수학적인 특징은 다음과 같다.

GCD * LCM = A * B

유클리드 호제법의 원리는 다음과 같다.

A를 B로 나눈 나머지를 r이라고 했을 때, GCD(A, B) = GCD(B, r)와 같다는 것이다.

 

예를 들어 13과 17의 최대공약수를 구해보자.

17 % 13 = 4

13 % 4 = 1

4 % 1 = 0이므로 최대공약수는 1이다.

위의 수학적 특징을 이용하여 최소공배수를 구하면 1 *LCM = 13 * 17 이므로 최소공배수는 181이다.

 

21과 14의 최대공약수를 구해보자.

21 % 14 = 7

14 % 7 = 0 이므로 최대공약수는 7이다. 

7 * LCM = 21 * 14이므로 최소공배수는 42이다

 

코드로 구현하면 다음과 같다.

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

재귀를 사용하지 않는 방법은 다음과 같다.

const getGCD = (a, b) => {
  while (b > 0){
    const r = a % b;
    a = b;
    b = r;
  }
  return a;
}

 

---

관련문제 풀이

https://lazyhysong.tistory.com/entry/JS-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-N%EA%B0%9C%EC%9D%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

[JS] 최소공배수 구하기 - N개의 최소공배수