[알고리즘] 유킬리드 호제법

개념

호율적으로 최대공약수를 구하는 방법이다. O(log n)의 시간복작도를 가진다. 

 

https://velog.io/@corone_hi/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%9E%AC%EB%B2%95

최대공약수를 구하는 원리는 위의 그림과 같이 간단하다. 

나누는 수를 나머지로 나누는 과정을 반복하고 나머지가 0이 나올 때의 나누는 수가 구하려는 최대공약수가 된다.

 

 

구현

int gcd(int a, int b)
{
	if(b == 0)
    	return a;

	if(a % b == 0)
    	return b;
    else
    	return gcd(b, a % b);
}