[Algorithms] Euclidean Algorithm | 유클리드 호제법

Euclidean Algorithm

유클리드 호제법

- 최대 공약수를 빠른 시간내에 산출할 수 있는 알고리즘이다.

---

Mechanism (원리)

* Notation
\(GCD(a, b) \equiv a\)와 \(b\)의 최대 공약수
(Greatest Common Divisor)

\(LCM(a, b) \equiv a\)와 \(b\)의 최소 공배수
(Lowest Common Multiple)

Theorem. \(A = q\cdot B + r\) 일 때, \(GCD(A, B) = GCD(B, r)\) 이다.
(단, \(0 \leq r < B < A\) 이다.)

---

Implementation (구현)

* C++

typedef int type;

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

type gcd(type a, type b)
{
    if (a < 0 || b < 0)
        throw "wrong input: Not allowd negative number";
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    if (a == b)
        return a;
    if (a < b)
        swap(&a, &b);

    type dividend = a;
    type divisor = b;
    type result;
    while (divisor > 0)
    {
        result = divisor;
        divisor = dividend % divisor;
        dividend = result;
    }

    return result;
}

type lcm(type a, type b)
{
    return a * b / gcd(a, b);
}

* Prolog

gcd(U, V, U) :- V=0.
gcd(U, V, X) :- V>0,
    Y is U mod V,
     gcd(V, Y, x).