유클리드 호제법(Euclidean algorithm)

1. 개념

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

호제법이란 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘이다.

2개의 자연수 A B (A>B)에 대해 A를 B로 나눈 나머지를 r이라고 했을 때 A와 B의 최대공약수는 B와 r의 최대공약수와 같다는 성질을 이용한다.

2. 구현

1) 재귀호출

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

2) 반복문

int gcd(int a, int b)
{
    while (b > 0)
    {
        int q = a;
        a = b;
        b = q % b;
    }
    return a;
}

* 응용

유클리드 호제법을 응용하면 최소공배수 또한 구할 수 있다. 간단하게 곱하고 나누어주는 방식으로

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

[유클리드 호제법 예제 : http://gyutts.tistory.com/120]