JavaScript 최소공배수 & 최대공약수 구하기

zwundzwzig·2022년 11월 8일

JavaScript algorithm

algorithm

목록 보기

2/12

자바스크립트로
최대공약수(Greatest Common Divisor) & 최소공배수(Largest Common Multiple)
구하기

최대공약수 (GCD)

정수인 두 수의 공약수 중 가장 큰 수.
즉, 두 수를 동시에 나눌 수 있는 수 중 가장 큰 수이다.

let getGCD = (num1, num2) => {
  let gcd = 1;

  for(let i=2; i <= Math.min(num1, num2); i++){
      if(num1 % i === 0 && num2 % i === 0) gcd = i;
  }
  
  return gcd;
}

위 식과 같이 for문과 Math 함수의 min 메소드를 활용해 최대공약수를 구할 수 있다.

유클리드 호제법

최대공약수를 구하는 알고리즘으로 유클리드 호제법이 있다.
수학 시간에 배운 '그분'의 호제법 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

원리는 다음과 같다.

두 수를 나눈 나머지를 r이라고 할 때, 두 수 중 작은 수와 r의 최대공약수가 두 수의 최대공약수와 같다.
이 과정을 반복하다 나머지가 0이 될 때 나누는 수가 두 수의 최대공약수인 것.

유클리드 호제법에 재귀 방식을 활용해 최대공약수를 한 줄로 구현할 수 있다.

let getGCDwithRecursive = (num1, num2) => (num1 % num2 ? getGCD(num2, num1 % num2) : num2);

재귀 함수가 아니어도 물론 표현할 수 있다.

let getGCDwithWhile = (num1, num2) => {
  while(num2 > 0){
    let r = num1 % num2;
    num1 = num2;
    num2 = r;
  }
  return num1;
}

최소공배수 (LCM)

정수인 두 수의 공배수 중 가장 작은 수.
즉, 두 수를 곱한 값을 최대 공약수로 나눈 수이다.

let getLCM = (num1, num2) =>{
  let lcm = 1;
   
  while(true){
    if((lcm % num1 == 0) && (lcm % num2 == 0)) break;
    lcm++;
  }
  return lcm
}

두 수를 곱한 값을 최대공약수로 나눈 수이기 때문에, 사실 최대공약수만 알아도 최소공배수를 구할 수 있다.

예시 - programmers : 분수의 덧셈

첫 번째 분수의 분자와 분모인 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2.
위 네 값이 매개변수인 함수 solution.
두 분수를 더한 값을 기약 분수로 나타낼 때,
분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

생각의 흐름

우선 두 분모의 최소공배수를 구한 뒤, 최소공배수를 각 분모 값으로 나눈 두 개의 값을 해당 분자와 곱한 변수를 구해 문제를 해결하려 했다.

function solution(denum1, num1, denum2, num2) {
 let lcm = 1;
    
 while(true) {
     if ((lcm % num1 === 0) && (lcm % num2 === 0)) {
        break;
     }
     lcm++;
 }; // 최소공배수 구하기

 const first = lcm / num1;
 const second = lcm / num2;
 const numerator = first*denum1 + second*denum2;
 const getGCD = (a, b) => a % b === 0 ? b : getGCD(b, a % b);
  // 최대공약수 구하기
 const gcd = getGCD(numerator, lcm);
  // 기약분수로 만들기
 return [numerator / gcd, lcm / gcd];
}