유클리드 호제법(Euclidean Algorithm)

유클리드 알고리즘(Euclidean Algorithm)

최대공약수를 구하는 알고리즘으로, 일반적으로 사람이 최대공약수를 구할 경우 직관적으로 구할 수 있지만 컴퓨터는 그렇지 않다. 이 경우 유클리드 알고리즘을 사용하면 컴퓨터에서 손쉽게 최대공약수를 구할 수 있다.

유클리드 알고리즘

임의의 두 정수 u, v에 대해 (1) v가 u보다 크다면 v와 u의 값을 바꾼다. (2) u = u - v  (3) u가 0이면 v가 최대공약수, 0이 아니면 (1)로 돌아간다.

소스코드

#include 

using namespace std;

int main(void)
{
	int u = 280;
	int v = 30;
	int tmp = 0;

	while (u > 0) {
		if (v > u) {
			tmp = u;
			u = v;
			v = tmp;
		}
		u = u - v;
	}

	cout << v << endl;
	return 0;
}

개선된 유클리드 알고리즘

위에서 설명한 알고리즘의 경우 뺄셈을 기반으로 동작하는데, u와 v의 차이가 클 경우 많은 뺄셈 연산을 수행해야 하는 단점이 존재한다. 그러나 여기서 규칙을 잘 살펴 보면 뺄셈의 결과는 나눗셈의 나머지를 구하는 것을 알 수 있다. 개선된 알고리즘은 아래와 같다.

임의의 두 정수 u, v에 대해  (1) v가 0이 아니면   (1.1) u = u % v    (1.2) u와 v를 교환    (1.3) (1)로 돌아감  (2) v가 0이면 u가 최대공약

 

소스코드

int main(void) {
	int u = 280;
	int v = 30;
	int tmp = 0;

	while (v > 0) {
		tmp = u % v;
		u = v;
		v = tmp;
	}

	cout << u << endl;
	return 0;
}