(프로그래머스) 최대공약수와 최소공배수

최대공약수와 최소공배수

문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
(출처)

다음 성질을 이용해 최대공약수를 구하면 최소공배수는 어렵지 않게 구할 수 있다.

두 수의 곱 = 최대공약수 * 최소공배수

최대공약수를 구하는 방법으로 두가지 방법을 사용해보았다.

(1)

  let LCM, GCD;
  let i = 1;
  let a, b;

  a = Math.max(m, n);
  b = Math.min(m, n);

  for (i = a; i > 0; i--) {
    if (a % i === 0 && b % i === 0) {
      GCD = i;
      break;
    }
  }
  LCM = (a / GCD) * b;
  return [GCD, LCM];

GCD가 최대공약수, LCM이 최소공배수이다.
먼저 a를 두 수 중 더 큰 수로 정한다.
그다음 작은 수인 b부터 1씩 줄이며 나누어보기 시작해 동시에 나누어 떨어지는 수를 최대공약수라고 한다.
큰 수가 아닌 작은 수부터 나눠보는 이유는 큰 수와 작은 수 사이에 있는 수는 절대 작은 수의 약수가 될 수 없기 때문이다.

(2)

let a, b, c;
  a = Math.max(m, n);
  b = Math.min(m, n);
  while (b !== 0) {
    c = a % b;
    a = b;
    b = c;
  }
   return [a, (n * m) / a];

다음은 유클리드 호제법을 이용해보았다.
유클리드 호제법은 아래의 과정을 나머지가 0이 될 때까지 반복했을 때 나오는 값이 두 수의 최대공약수가 된다는 알고리즘이다.
(a)큰 수를 작은 수로 나누어 나오는 나머지를 구한다.
(b)작은 수를 (a)에서 구한 나머지로 나누어 나머지를 구한다.
그래서 나머지가 0이 될때까지 나누어 나온 값 a를 최대공약수라고 보았다.