[Algorithm] 유클리드 호제법

유클리드 호제법이란?

두 개의 정수 a, b에 대하여 a, b의 최대공약수를 찾는 방법을 말한다.

 

 

유클리드 호제법의 원리

a가 b보다 크다고 할 때, a = bq + r이 성립한다.

a, b의 최대공약수를 G라고 하면, a = GA, b = GB가 성립한다.

이를 위 식에 대입하면 GA = GBq + r이다.

여기에서 r = G(A - Bq)로, a와 b와 r의 최대공약수가 G임을 알 수 있다.

 

 

알고리즘

위 원리를 이용하여, r = 0일 때 까지 작업을 반복한다.

(r = 0인 경우는 나눠 떨어지는 경우)

int gcd(int a, int b) {
	int r = 0;

	while (b > 0) {
		r = a % b;
		a = b;
		b = r;
	}

	return a;
}

 

출처 : https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95