참고자료|JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기

---

최대공약수

• 두 수 A와 B의 공통된 약수 중 가장 큰 수
• 2부터 min(A,B)까지 모든 정수로 나눠서 구하기

let getGCD = (num1, num2) => {
  let gcd = 1;
  
  for (let i=2; i<=Math.min(num1, num2); i++) { // Math.min(A,B)는 A,B중 더 작은 수를 return 하는 함수
    if (num1 % i === 0 && num2 % i === 0) {
      gcd = i;
    }
  }
  
  return gcd;
}

최소공배수

• 두 수 A, B 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수
• 두 수 A, B를 lcm으로 나누었을 때 나머지 값이 둘 다 0인지 비교한다.

let getLCM = (num1, num2) => {
  let lcm = 1;
  
  while(true) {
    if((lcm % num1 == 0) && (lcm % num2 == 0)) {
      break;
    }
    lcm++; // lcm++ 해가면서 두 수를 나눈 나머지 값이 둘 다 0이 될 때까지 반복하다가 break
  }
  return lcm
}

유클리드 호제법

function solution(num1, num2) {
  const gcd = (a,b) => a % b === 0 ? b : gcd(b, a % b); // 최대공약수
  const lcm = (a,b) => a * b / gcd(a,b); // 최소공배수
  return [gcd(num1, num2), lcm(num1, num2)];
}

• const gcd = (a,b) => a % b === 0 ? b : gcd(b, a % b) : a를 b로 나눈 나머지가 0인 경우 b가 최대공약수가 된다. 나머지가 0이 될 때까지 b를 a를 b로 나눈 값의 나머지로 나눈다.
  

• const lcm = (a,b) => a * b / gcd(a,b) : num1 * num2 = gcd * lcm과 같다는 원리를 이용함. 즉, lcm = (num1 * num2) / gcd인 것.