[알고리즘] 유클리드 호제법 : 최대공약수(GCD)와 최소공배수(LCM)

용어 설명

최대공약수 (Greatest Common Divisor) : 공통된 약수 중 가장 큰 수

최소공배수 (Least Common Multiple) : 공통된 배수 중 가장 작은 수

유클리드 호제법 : 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘

 

최대공약수(GCD) 구하기 (JavaScript)

2개의 자연수 a, b(a > b)에 대해서, a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

// 최대 공약수를 구하는 함수 (유클리드 호제법: Euclidean algorithm)

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

gcd(m,n) // m과 n의 최대공약수

 

최소공배수(LCM) 구하기 (JavaScript)

2개의 자연수 a, b(a > b)에 대해서, a와 b의 곱은 최대공약수와 최소공배수의 곱과 같다

a * b = GCD * LCM

LCM = (a * b) / GCD

 

// 최대 공약수를 구하는 함수 (유클리드 호제법: Euclidean algorithm)

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

(m * n) / gcd(m, n)  // m과 n의 최소공배수