유클리드 호제법, 최대공약수를 구하는 알고리즘

유틀리드 호제법 / 유클리드 알고리즘 / Euclidean algorithm

두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 알고리즘

두 양의 정수 a, b (a > b) 에 대하여 a = bq + r (0 <= r <= b)이라 하면,
a, b 의 최대공약수는 b, r 의  최대공약수와 같다.

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

r = 0이라면, a,b의 최대공약수는 b가 된다.

---

예제 (Java)

 

반복문

int getGCD(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

 

재귀

int getGCD(int a, int b) {
    if (b == 0) {
        return a;
    }
    return getGCD(b, a % b);
}

 

 

활용: 최소공배수 구하기

최소공배수(LCM)는 GCD를 알면 쉽게 구할 수 있다.

LCM(a, b) = (a × b) / GCD(a, b)