최대공약수와 최소공배수

1. 코드 정리

function solution(n, m) {
  let answer = [];
  if (n >= m) {
    for (let i = n; i >= 1; i--) {
      if (n % i === 0 && m % i === 0) {
        answer.push(i);
        break;
      }
    }
  } else {
    for (let i = m; i >= 1; i--) {
      if (n % i === 0 && m % i === 0) {
        answer.push(i);
        break;
      }
    }
  }
  for (let i = n; i <= n * m; i++) {
    if (i % n === 0 && i % m === 0) {
      answer.push(i);
      break;
    }
  }
  return answer;
}

---

Math.min(num1, num2)을 이용하면 더 쉽게 구할 수 있었을 텐데... 나중에서야 생각난 메서드;;

최대공약수(GCD, Greatest Common Divisor)

• 두 자연수의 공통된 약수들 중에서 가장 큰 수

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;
}

최소공배수(LCM, Least Common Multiple)

• 두 자연수의 배수들 중 공통된 가장 작은 수

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

---

다른 사람의 풀이를 보다 유클리드 호제법을 활용했길래 재미있어 보여 정리해봤다.

유클리드 호제법

유클리드 호제법의 기본 원리는 num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것

r이 0이라면, 그 때의 num2가 최대 공약수!

num1=32, num2=24이라고 가정하면, GCD(32,24) = GCD(24,8) = GCD(8,0)

GCD=8

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

최소공배수는
num1 * num2 = gcd * lcm 과 같다는 원리를 이용
lcm = (num1*num2) / gcd

유클리드 호제법 정리

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)];
}