유클리드 알고리즘

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

 1. 임의의 정수  m 과 n을 입력받는다.
 2. m 을 n 으로 나누어 나머지를 r 에 입력한다.
 3. r 이 0 이면 n 이 최대 공약수가 된다. r 이 0 이 아니면 m 에 n 을 입력하고, n 에 r 을 입력한 후 2번부터 다시 반복한다.

int gcd (int m, int n) { int r; if (n > m) /* 두 수를 swap 한다 */ { r = m; m = n; n = r; } while (1) { r = m % n; if (r == 0) break; m = n; n = r; } return n; }

위의 C 코드는 아주 단순한 코드이지만 상당히 심플하게 최대공약수를 구할 수 있도록 되어있다.

이 코드보다 단순한 코드도 존재하지만 이 코드는 유클리드 알고리즘의 설명을 위해 알고리즘에 충실하게 짜여진 코드이다.
 
우선 두 수 중 큰 수를 m 에 입력하고 작은 수를 n 에 입력한다.(뭐 처음부터 그렇게 되어 있다면 swap이 필요없겠지만 말이다)

이제는 좀더 코드를 알차게 만들어보자

1. while 문에서 if() break; 문은 while문의 조건으로 빼면 더 좋지 않을까?
2. swap 코드는 필요한 코드인가 ?

위 두가지 문제를 해결하면
int gcd (int m, int n) { int r; while (n > 0) { r = m % n; m = n; n = r; } return m; }

또 다른 방법은 재귀를 사용하는 방법이 있다.

int gcd (int m, int n) { if (n == 0) return m; return gcd (n, m % n); }