[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;
}

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