[C] 최대 공약수 구하는 함수 (유클리드 알고리즘)

int get_gcd(int u, int v)
{
	int temp = 0;

	while(u)
	{
		if(u < v)
		{
			temp = u; u = v; v = temp;
		}

		u = u - v;
	}

	return v;
}

유클리드 알고리즘
GCD(280, 30) = GCD(250, 30)
= GCD(220, 30)
= GCD(190, 30)
... 이런 식으로 큰 수에서 작은수를 계속해서 빼 나간다.
= GCD(40, 30)
= GCD(10, 30) // 이렇게 앞의 수가 뒤의 수보다 작아지면 두 수를 교환
= GCD(30, 10)
... 다시 반복해서 빼 나간다.
= GCD(20, 10)
= GCD(10, 10)
= GCD(0, 10) // 앞의 수가 뒤의 수보다 작아졌기 때문에 두 수를 교환
= GCD(10, 0) // 뒤의 수가 0이 되면 앞의 수가 최대 공약수
// 이것이 최대 공약수 구하는 유클리드 알고리즘 원리

여기에서 작아질때 까지 빼는 내용이 반복되므로 이 과정을 % 연산자를 이용해서 한번으로 줄이면

int get_gcd(int u, int v)
{
	int temp = 0;

	while(v)
	{
		temp = u % v;
		u = v;
		v = temp;
	}

	return u;
}

로 더 간단하게 표현할 수 있다.