[프로그래머스] 최대공약수와 최대공배수

문제 설명

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

 

제한 사항

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

 

ex)

n: 3, m: 12, return [3, 12]

 

 

최대 공약수: 두 수 n, m의 공통된 약수 중에서 가장 큰 수

최소 공배수: 두 수 n, m의 공통된 배수 중에서 가장 작은 수

 

이 문제를 풀기 위해서는 다음과 같은 원리를 이용할 수 있다.

- 유클리드 호제법

- num1 * num2 = gcd * lcm

 

유클리드 호제법

1. n>m일 때, 큰 수(n)를 작은 수(m)로 나눈다. (n % m = R1)

2. 나누는 수 m을 나눈 나머지 R1로 나눈다. (m % R1 = R2)

3. R1을 R2로 나눈다. (R1 % R2 = R3)

이 과정을 반복해서 Rn이 0이 된다면 나누는 수(Rn-1)가 최대공약수이다.

 

Answer

function solution(n, m) {
    const gcd = (a, b) => a%b === 0 ? b : gcd(b, a%b);
    const lcm = (a, b) => (a*b) / gcd(a,b);
    
    return [gcd(n,m), lcm(n,m)]
}