[ 알고리즘 ] 유클리드 호제법

유클리드 호제법 : 두 수 a b가 있을 떄, a를 b로 나눈 나머지가 r일 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정의 반복 속에 나머지가 0이 되었을 때 나누는 수가 두 수 a b의 최대공약수가 된다.

 

// 정수 x, y 의 최대공약수 반환
// 유클리드 호제법 : 두 수 a b가 있을 떄, a를 b로 나눈 나머지가 r일 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정의 반복 속에 나머지가 0이 되었을 때 나누는 수가 두 수 a b의 최대공약수가 된다.
int gcd(int x, int y) {
    if(y == 0)
        return x;
    else
        return gcd(y, x % y);
}

자연수를 넘겨줘야 하겠지만, 0과 n의 최대공약수는 n인 사실이 있다.

또한 위 코드에는 x > y 라는 잠재적 기준이 있지만, 그렇지 않을 경우 알아서 바뀌긴 한다. 따라서 위 코드에 0을 넘겨줘야할 때 0이 나누는 수가 될 수 있으니 주의해서 처리해줘야 함.

 

// GCD를 while문으로 구함. 재귀로도 가능.
int gcd(int a, int b) {
    
    int temp;
    
    while(b != 0) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}