javascript로 최대공약수, 최소공배수를 유클리드 호제법으로 구하기

유클리드 호제법

유클리드가 발견한 알고리즘으로 두 수가 있다면 최대공약수를 구하는 알고리즘이다.

최대공약수

두 양의 정수 a, b (a > b)가 있고 a % b의 나머지를 r이라고 한다면, a, b의 최대공약수는 b, r의 최대공약수와 같다.

gcd(a,b) = gcd(b, r)

예를 들어, 48와 21의 최대공약수를 구하려면

• 48 % 21 => 6
• 21 % 6 => 3
• 6 % 3 => 0

이 되므로 최대공약수는 3이 되는 과정을 거친다.

이를 javascript 재귀함수로 나타내보면 아래와 같다.

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

// example
console.log(gcd(48, 21)) // 3

최소공배수

최소공배수는 간단하다. 두 수 a, b가 있다면 a와 b를 곱한 값을 최대공약수로 나누면 된다.

이를 자바스크립트 코드로 나타내보자.

funciton lcd(a, b) {
  return (a * b) / gcd(a, b)
}