최대공약수 - 유클리드 호제법

최대공약수를 구해야 하는 경우가 있다.

int Calc(int a, int b)
{
    int num, flag = 1;
    if(a >= b) num=b;
    else num=a;
    
    while(flag == 1){
        if(a%num == 0 && b%num == 0){
            flag = 0;
            break;
        }
        num--;
    }
    return num;
}

위의 함수는 최대공약수를 구하는 함수다. num의 경우 두 숫자 a와 b중 작은숫자로 부터 시작하여

디카운트를 진행하여 주어진 두 숫자를 모두 나누었을때 나머지가 0인 경우. 즉, num이 가장큰 공통 약수가 되는 경우를 찾는 매우 간단한 코드다.

 

하지만 위의 코드의 경우 카운트를 하나씩 줄여가면서 일일이 a와 b에 연산을 진행해야하므로 결과값을 얻는데 시간이 오래 걸린다.

 

유클리드 호제법

 위의 연산을 보완할 수 있는 방법이 아래의 유클리드 호제법이다.

유클리드 호제법은 두 수에서 큰수로 작은수로 나누었을때 나머지가 0이 될때까지 직전 연산의 작은수를 나머지로 나우면서 반복적으로 진행하는 방법이다.

 

big_number0 = small_number0 x multi0 + remain0
small_number0 = remain0 x multi1 + remain1
remain0 = remain1 x multi2 + remain2
remain1 = remain2 x multi3 + remain4
                              ...
remain(n-1) = remain(n) x multi(n+1) + 0

 

위와 같이 진행될 수 있으며 마지막에 나머지가 0일때 작은수가 최대공약수가 된다.

 

이를 코드로 옮기면 다음과 같다.

int Calc(int small, int big)
{
    int remain=0, rtnval, flag = 1;
    while(flag){
        remain = big%small;
        if(remain == 0){
            rtnval = small;
            flag = 0;
            break;
        }else{
            big = small;
            small = remain;
        }
    }
    return rtnval;
}

위와 같이 진행할 경우 시간복잡도가 최초 함수보다 현저히 줄어든다.