[자료구조와 알고리즘] 유클리드 알고리즘

유클리드 알고리즘

최대공약수를 구하는 알고리즘이다.

GCD 관련 법칙

• if u>v GCD(u, v) == GCD(u - v, v)
• 교환법칙 GCD(u, v) == GCD(v, u)

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

1. v가 u보다 크다면 v와 u의 값을 바꾼다.
2. u = u - v
3. u가 0이면 v가 최대공약수 0이 아니면 1로 돌아감

알고리즘의 구현

int get_gcd(int u, int v)
{
    int t;
    while (u>0)
    {
        if(u<v)
        {
            t=u; u=v; v=t;
        }
        u=u-v;
    }
    return v;
}

• 뺄셈 기반의 알고리즘
  • 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가 최대공약수

int get_modulus(int u, int v)
{
    int t;
    while (v>0)
    {
        t = u%v;
        u = v;
        v = t;
    }
    return v;
}

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