유클리드 알고리즘 (gcd, 최대공약수)

유클리드 알고리즘이란?

유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(gcd)를 구하는 알고리즘이다.

원리

유클리드 알고리즘은 다음과 같은 원리로 동작한다.

 

1. 임의의 두 자연수 a, b가 주어진다. (둘 중 큰 값이 b라고 가정한다.)

2. a와 b를 나눈 나머지를 구한다. 이 결과값을 n이라고 한다. (n = a % b)

3. n이 0일때 a가 최대공약수(gcd)가 된다.

4. 만약 n이 0이 아닌 경우, b에 n값을(b = n), a에 b값을(a = b) 넣고 2부터 반복한다.

구현

두가지 방법으로 구현이 가능하다.

 

반복문을 이용한 구현

int gcd(int a, int b) {
    int n;
    
    // b에 큰 값을 위치시키기 위한 조건문
    if(a > b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    // 유클리드 알고리즘 부분
    // b가 0이 되는 순간의 a가 최대공약수(gcd)가 된다.
    while(b != 0) {
        n = a % b;
        a = b;
        b = n;
    }
    
    return a;
}

 

재귀를 이용한 구현

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