[Algorithm] 유클리드 호제법 - 최대공약수(GCD), 최소공배수(LCM) 구하기

유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.

정의

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

코드

재귀 호출

b 가 0이 될 때까지 계속해서 재귀 호출을 해주고, 0이 되면 a를 반환한다.

// 단, a가 b보다 커야함.
function gcd(a, b) {
  return b ? gcd(b, a % b) : a;
}

반복문

// 단, a가 b보다 커야함.
function gcd(a, b) {
  while (b > 0) {
    let tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

설명

106과 16의 최대공약수 - gcd(106, 16)

SEQ	gcd(a, b)	a	b	a % b(remainder)
1	gcd(106, 16)	106	16	10
2	gcd(16, 10)	16	1	6
3	gcd(10, 6)	10	6	4
4	gcd(6, 4)	6	4	2
5	gcd(4, 2)	4	2	0

a % b가 0이 되면 b의 값 2가 최대공약수가 된다.

그림

최소공배수

최소공배수 = 두 자연의 곱 / 최대공약수

위의 예시로 106과 16의 최소공배수는 848 (106 * 16 / 2) 이 된다.

두 수의 최소공배수(LCM), 최대공약수(GCD) 구하기

function calculator(n, m) {
  const num = gcd(n, m);
  return [num, (n * m) / num];
}

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

console.log(calculator(106, 16)); // [2, 848]