[CODING TEST]::LV1 최대공약수와 최소공배수

[문제]

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

[제한]

• 두 수는 1이상 1000000이하의 자연수입니다.

[입출력 예]

n	m	return
3	12	[3, 12]
2	5	[1, 10]

[입출력 예 설명]

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

[answer]

function solution(n, m) {
  return [gcd(n, m), lcm(n, m)];
}
//최대공약수 유클리드 호제법
let gcd = (n, m) => {
  if (m === 0) return n;
  return n > m ? gcd(m, n % m) : gcd(n, m % n);
};
//최소 공배수 = 주어진 인자들의 곱 후 최대공약수로 나누기
let lcm = (n, m) => {
  return (n * m) / gcd(n, m);
};

문제의 해석

최대공약수를 구하는 방법 - <유클리드 호제법>

• 유클리드 호제법의 원리

  1) 두 수 중에서 큰 수를 작은 수로 나눈다.
  2-1) 나누고 난 나머지가 0 이면, 작은 수가 최대 공약수가 된다
  2-2) 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눈다.
  3) 나머지가 0이 될때까지 반복하면, 그 수가 최대공약수가 된다.

최소공배수를 구하는 방법

• 주어진 두 수의 곱하기를 한 후 최대공약수로 나누면 된다.

[codesandbox]
https://codesandbox.io/s/coding-test-daily-40-2rml4r