유클리드 호제법(최소공배수)

• 프로그래머스 연습문제를 풀다 발견한 최소공배수 알고리즘
  두 수의 최대공약수를 먼저 구한 후, 두 수의 곱을 최대공약수로 나누면
  최소공배수가 나온다.

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

원리

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

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