[알고리즘] 최대공약수(gcd), 최소공배수(lcm)

최대공약수(유클리드 호제법)

수학적 성질: 어떤 수 x가 a와 b를 모두 나눌 수 있다면, x는 b%a도 나눌 수 있다. 그 반대로 성립한다.

// num1 <= num2
function gcd(num1, num2) {
  if(num1 == 0) return num2;
  return gcd(num2 % num1, num1);
}

 

최소공배수

// 두 수의 곱 / 최대공약수
function lcm(num1, num2) {
  return (num1 * num2) / gcd(num1, num2);
}