유클리드 호제법 (최대공약수, 최소공배수 찾기)

유클리드 호제법

유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

유클리드 호제법에 의하면 A와 B 두 수의 최대공약수를 구할 때,
A = Bq+r 의 식으로 만든 뒤 B와 r의 최대공약수를 구하는 문제로 바꿀 수 있다.
연속되는 B, r의 최대공약수에 대해서도 B = rq+r2 와 같이 재귀가 가능하다.

최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다.

---

최대 공약수 구하기

1112와 695의 최대공약수 계산

일반적으로는 최대 공약수를 구하기 위해서 소인수분해를 진행해야 한다.

1112 = 139 X 2 X 2 X 2

695 = 139 X 5

위와 같이 두 수를 소인수분해 한 후, 공통된 소수를 찾으면 최대공약수를 구할 수 있다.
두 수의 최대공약수(GCD)는 139이다.
하지만 이렇게 최대공약수를 구하는 방법은 소인수분해하기 어려워진다는 단점이 있다.
효율적으로 최대공약수를 구하기 위해서는 유클리드 호제법을 활용한다.

---

유클리드 호제법 사용

유클리드 호제법은 MOD 연산을 사용한다.

1. 먼저 큰 수를 작은 수로 나눈 나머지를 구한다.(=MOD 연산)
   1112 mod 695 = 417

2. 그 다음, 나눴던 수와 나머지로 또 MOD 연산을 한다.
   695 mod 417 = 278

3. 위 과정을 계속 반복한다.
   417 mod 278 = 139
278 mod 139 = 0

4. 나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139가 최대 공약수가 된다.

코드

반복문

const GCD = (a, b) => {
	let temp;
  
  	while (b) {
    	temp = a % b;
      	a = b;
      	b = temp;
    }
  
  	return a;
}

재귀함수

const GCD = (a, b) => {
	return b ? GCD(b, a % b) : a;
}

최소 공배수 구하기

최대공약수를 구했다면, 아래와 같은 최소공배수의 성질을 이용해서 쉽게 구할 수 있다.

두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

let lcm = a * b / GDC(a, b);