최대공약수 / 최소공배수

최대공약수 구하기

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

a,b의 순서에 관계없이 a%b가 0이 될때 비로소 최대공약수가 나온다.

최소공배수 구하기

function lcm(a,b){
    return a*b / gcd(a,b);
}

전체 곱에서 최대공약수를 나누어 준다.

여러개의 값에 대한 최소공배수 구하기

ex) [2,6,8,14]에 대한 최소공배수는 168이다.

function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}
function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

생각해야 할 점

ex) [3,6,5,14]의 최소공배수는 [6,5,14]의 최소공배수이고 [30,14]의 최소공배수이다.

즉, 2개씩비교하여 나온 최소공배수를 계속해서 만들어 2개씩 비교를 마지막까지 한 결과가 최종 최소공배수이다.

이를 위해서는 반복을 하면서 해당 값을 반복해서 사용하는 reduce 함수가 사용에 알맞아서 위와 같이 사용한다.