유클리드 알고리즘
유클리드 알고리즘은 주어진 두 정수 사이에 존재하는 최대공약수를 구하는 알고리즘이다. 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 코드는 아주 단순한 코드이지만 상당히 심플하게 최대공약수를 구할 수 있도록 되어있다. 이 코..
2008.12.06