유클리드 호제법(최대공약수)

유클리드 호제법?

두 수의 최대공약수를 구하는 알고리즘
여기서 호제법이란? 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

접근법

1. 큰 수를 작은 수로 나눈 나머지를 구한다.

   1112 % 695 = 417

2. 나눴던 수와 나머지로 또 나머지 연산을 한다.

   695 % 417 = 278

3. 이 과정을 계속 반복한다. 이때 나머지가 0이 됐을 때 마지막 계산에서 나누는 수로 사용된 값이 최대공약수가 된다.

   417 % 278 = 139      278 % 139 = 0

ex) 최대공약수 & 최소공배수 구하기 문제

function solution(n, m) {
  const greatest = (a, b) => {
    if (b === 0) return a;
    return greatest(b, a % b);
  };

  const least = (a, b) => (a * b) / greatest(a, b);
  return [greatest(n, m), least(n, m)];
}

console.log(solution(3, 12));

최소공배수는 입력값으로 주어진 자연수 2개를 곱하고 최대공약수로 나누면 구할 수 있다.