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

최대공약수(gcd)를 쉽게 구할 수 있게 해주는 공식.

 

숫자 a와 b가 주어진다고 했을때 두수의 최대 공약수 gcd(a,b)를 구하는 문제를 생각해보자.

 

a>b 라고 했을 때 $a = bq+r$ 꼴로 표현할 수 있는데,

$gcd(a, b) = gcd(b, r) $

이란것이 유클리드 호제법이다.

r = a%b는 b보다 작으므로 gcd(a,b)에서 gcd(b,r)로 순서가 바뀜에 주의하자.

(사실 gcd는 순서에 무관하나 이해를 위해 a>b라는 속성을 유지하는 것)

증명은 여기를 참고하자.

 

계속 위처럼 하다가 r==0이 되는 순간 즉 a가 b로 나눠떨어지는 순간 b를 리턴하면 된다.

 

위의 내용대로 구현한 코드는 다음과 같다.

int gcd(int a, int b) 
{
    while(1)     
    {         
    	int r = a%b;         
        if(r==0) return b;         
        a=b,b=r;     
    } 
}

 

그런데 위의 코드는 함수 종료부분에 return 코드도 없고 while(1)인것도 좀  그래서 살짝 정리하고 나면 인터넷에 많이 퍼져있는 다음 형태가 된다.(자료형도 좀 더 사용성 좋도록 long long으로 변경)

 

long long gcd(long long a, long long b) {
    while (b > 0)     
    {         
    	long long t = a % b;         
        a = b, b = t;     
    }     
    return a; 
}

 

재귀호출 버전

long long gcd(long long a, long long b) {
    return (b == 0) ? a : gcd(b, a%b);
}
 

 

 

여러수의 최대공약수 구하기

n개의 숫자에 대한 최대 공약수를 구할때는 단순히 루프를 돌면서 gcd를 반복하면 된다.

마치 max함수가 n개에 대해서 할때는 여러번 적용하듯이..

 

관련문제

http://codeup.kr/problem.php?id=4016

내 풀이

int gcd(int a, int b)
{
    int c;
    while (b) {
        c = a % b;
        a = b, b = c;
    }
    return a;
}
int main(void)
{
    int n = 3;
    int* d = new int[n + 1](); for (int i = 0; i < n; i++) scanf("%d", d + i);
    int v = gcd(d[0], d[1]);
    for (int i = 2; i < n; i++) v = gcd(v, d[i]);
    printf("%d\n", v);
    return 0;
}