프로그래머스, 자바스크립트) 최대공약수와 최소공배수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

풀이

최대공약수와 최소공배수를 구할때는 유클리드 호제법을 알면 쉽게 구할 수 있다.

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

유클리드 호제법, 위키피디아

 

최대 공약수를  구하고 나면 최소 공배수는 쉽게 구할 수 있다. 두 수의 곱을 최대 공약수로 나눈 수가 최소 공배수가 된다.

 

ex) 114 8

114/8 => 나머지는 2

8과 2의 나머지는 0으로 최대 공약수는 2가 된다.

 

그리고 114*8 = 912를 최대 공약수 2로 나눈 수가 456으로 최소 공배수가 된다.

let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

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)]; //최대공약수, 최소공배수
}