[알고리즘] GCD 최대공약수 구하기 알고리즘

1. 유클리드 알고리즘(Euclidean algorithm)

두 자연수의 최대 공약수(greatest common divisor)를 찾는 알고리즘을 뜻한다.

 

2. 유클리드 알고리즘 원리

두수 A와 B(A>B)가 있고 A를 B로 나누었을때 나머지가 C일 때

C가 0일경우 B가 최대 공약수이고 아닐경우 A = B 로 B = A % B로 하고 반복해서 C가 0일 될때까지 하면 된다.

 

ex) GCD(12, 8) -> GCD(8, 4) -> GCD(4, 0)  최소공배수 = 4

 

장점

• 최대공약수를 구하는 방법중 가장 간단한 방법인 1부터 min(A,B)까지 순서대로 찾는 방법의 시간 복잡도는 O(N)이지만 유클리드 호제법을 이용할 경우 O(Log N)으로 줄일 수 있다.

3. 구현(C/C++)

반복문을 통한 GCD 구하기

int GCD(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

 

재귀함수를 이용한 GCD 구하기

int GCD(int a, int b) {
	return b == 0 ? a : GCD(b, a % b);
}

 

4. 최소공배수 구하기

int LCM(int a, int b) {
	return a * b / GCD(a, b);
}

 

참고

https://m.blog.naver.com/eandimath/221704180761

https://coding-factory.tistory.com/599​