유클리드 호제법 알고리즘

[초딩코딩(112.160)]

유클리드 호제법이

a > b > 0 , 이고,  gcd(a, b) 라는 함수가 있을때... 

a mod b = r 이라면, 

gcd(a, b) = gcd(b, r) 이 같다는 거잖냐..

이거를 가지고 알고리즘을 짠다고 할때, 어떻게 짜야 가장 효율적인거냐?

1.번

int gcd1(int x, int y) {

        while( x != 0) {

            if(x < y)

              swap(x, y) ;

            x %= y;

        }

        return y;

}

2.번

int gcd2(int x, int y) {

  while(x != y) {

    if(x > y)

      x = x - y;

    else

      y = y - x;

  }

  return x;

}

3.번

int gcd3(int x, int y) {

  int mod = x % y;

  while(mod > 0) {

    x = y;

    y = mod;

    mod = x % y;

  }

  return y;

}