유클리드 호제법

아래 영상을 참고해 작성했습니다.

https://www.youtube.com/watch?v=Obs-HC5j5bI 

---

정의

자연수 a, b가 주어질 때

a와 b의 최대 공약수 (=gcd(a, b))를 구하는 방법

---

과정

gcd(A, B) = gcd(B, A % B)를 이용해 재귀적으로 구할 수 있습니다.

 

gcd(12345, 123)을 구해봅시다.

(B == 0이 될 때 A 값이 정답임)

---

증명

위의 영상으로 대체하겠습니다.

---

코드

매번 큰 비트가 사라지기 때문에

O(max(log a, log b)) 만에 gcd(a, b)를 구할 수 있습니다.

#include <cstdio>

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main()
{
	printf("%d\n", gcd(3 * 3, 3 * 1)); // 3
	printf("%d\n", gcd(17 * 3, 17 * 4)); // 17
}