[알고리즘] 유클리드 호제법

1. 유클리드 호제법

유클리드 호제법(또는 유클리드 알고리즘, Euclidean Algorithm)은 두 양의 정수의 최대공약수를 구하는 방법 중 하나이다.

여기서 호제라는 말은 서로 나눈다는 것을 의미한다.

 

---

2. 최대공약수의 정의

최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 정수의 공통 약수 중 가장 큰 양의 정수이다.

또한 최대공약수가 $1$인 두 정수를 서로소(coprime)라고 한다.

 

($0$과 어떤 정수 $a$의 최대공약수는 $a$로 정의할 수 있다. $0$은 모든 정수의 배수이기 때문이다.)

 

---

3. 최대공약수의 특징

두 정수 $a$와 $b$의 최대공약수 $\gcd(a, b)$에 대해, $ax + by = \gcd(a, b)$를 만족하는 정수 $x$, $y$가 존재한다.

 

---

4. 최소공배수의 정의

최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 양의 정수이다.

 

($0$과 어떤 정수 $a$의 최소공배수는 $0$으로 정의할 수 있다. $0$은 모든 정수의 배수이기 때문이다.)

 

---

5. 최소공배수의 특징

두 정수 $a$와 $b$의 최대공약수 $\gcd(a,b)$와 최소공배수 $\mathrm{lcm}(a,b)$에 대해 항상 $ab = \gcd(a,b) \cdot \mathrm{lcm}(a,b)$가 성립한다.

이를 이용하면 두 수의 최소공배수는 $\mathrm{lcm}(a,b) = \cfrac{ab}{\gcd(a,b)}$ 으로 구할 수 있다.

 

---

6. 유클리드 호제법을 이용하여 최대공약수와 최소공배수 구하기

(아래는 개인적으로 미리 설정해놓은 헤더 파일이다)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;

const double PI = M_PI;

 

유클리드 호제법에서는 $\gcd(a, b) = \gcd(b, a \bmod b)$를 이용하여 재귀적으로 두 정수 $a$와 $b$의 최대공약수를 구한다.

아래의 get_gcd 함수는 유클리드 호제법을 이용하여 두 정수 a 와 b 의 최대공약수를 계산한다.

ll get_gcd(ll a, ll b) {
    if (b == 0) return a;

    return get_gcd(b, a % b);
}

 

재귀로 구현한 위의 코드 대신 반복문으로 구현할 수도 있다.

ll get_gcd(ll a, ll b) {
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }

    return a;
}

 

get_lcm 함수는 위의 특징에서 언급한 $\mathrm{lcm}(a,b) = \cfrac{ab}{\gcd(a,b)}$를 이용하여 최소공배수를 계산한다. 최대공약수는 위의 get_gcd 함수를 그대로 활용했다.

오버플로우 문제가 발생할 가능성을 낮추기 위해 a 에서 최대공약수를 먼저 나눠준 후 b 를 곱해주었다.

ll get_lcm(ll a, ll b) {
    if (a == 0 || b == 0) return 0;

    return a / get_gcd(a, b) * b;
}

 

---

7. 참고 자료

1. https://ko.wikipedia.org/wiki/유클리드_호제법