1.3 유클리드 알고리즘

1. 최대공약수(Greatest Common Divisor)

주어지는 두 정수의 약수 중에서 가장 큰 공통약수

280과 30의 GCD는 10임

-> 280의 약수 : 1, 2, 3, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280

-> 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30

소인수분해를 통해 GCD를 구할 수 있음

-> 직관에 의존하는 방법이기 때문에 컴퓨터에 부적절함

 

2. GCD 관련 법

GCD관련 법칙

GCD(u,v) = GCD(u-v, v) if u > v

GCD(u,v) = GCD(v, u)

GCD(u, 0) = u

 

3. 유클리드 알고리즘

임의의 두 정수 u, v에 대해

(1) v가 u보다 크다면 v와 u의 값을 바꾸기

(2) u = u - v

(3) u가 0이면 v가 최대 공약수, 0이 아니면 (1)로 돌아감

 

3-1. 유클리드 알고리즘 구현

int get_gcd(int u, int v)

{

    int t; // u와 v를 교환하기 위한 임시 변수

    while (u) // u가 0보다 클 동안

    {

        if(u < v) // u가 v보다 크면

        {

            t = u; u = v; v = t; //u, v 교환

        }

        u = u - v;

    }

    return v;

}

 

4. 유클리드 알고리즘의 개선

뺄셈기반 알고리즘의 문제

-> u, v의 값 차이가 클 때 많은 뺄셈을 요구함

 

뺄셈의 결과는 나눗셈의 나머지를 구하는 것

-> GCD(u, v) = GCD(u%v, v) = GCD(v, u%v)

-> u%v < v

 

임의의 두 정수 u, v에 대해

(1) v가 0이 아니면,

    (1.1) u = u%v

    (1.2) u와 v를 교환

    (1.3) (1)로 돌아감

(2) v가 0이면 u가 GCD

 

4.1 개선된 알고리즘의 구현

int gcd_modules(int u, int v)

{
    int t;  // u와 v를 교환하기 위한 임시 변수

    while (v)  // v가 0보다 클 동안
    {
        t = u % v;
        u = v;
        v = t;
    }
    return v;
}



int gcd_recursion(int u, int v)

{
    if(v == 0)
    {
        return u;
    else
        return gcd_recursion(v, u%v);
    }