최대공약수 구하기 (유클리드 호제법)

수학적 이론은 여기로

 

1. 뺄셈을 이용한 구현

최악의 경우의 수: gcd(x, 1)

시간복잡도: \( log(max(a,b)) \)

int gcd(int a, int b)
{
    if (a == b) return a;

    if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

 

 

2. 나머지 연산자를 이용한 구현

시간복잡도: \( log(a + b) \)

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