[C언어 알고리즘] 유클리드 호제법을 이용한 최대공약수 구하기.

호제법이란, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

일반적으로 최대공약수를 구하기 위해서는 두 수를 소인수분해 하여서 공통된 수를 찾아야한다.

ex)
184 = 2 * 2 * 2 * 23
 42 = 2 * 3 * 7
GDC = 2

하지만 이러한 방식은 수가 커질수록 구하기가 힘들어진다는 단점이 있다.

 

유클리드 호제법은 이러한 수고를 덜어준다.

간단하게 설명을 해보겠다.

구하고자하는 수 a, b가 있다고 가정해보자. (단 a > b)

그리고 a를 b로 나눈 수를 c라고 할 때, 다시한번 b를 c로 나눈다.

이러한 과정이 반복되면 마지막에 나머지가 0이 되는 몫이 있을 것이다.

그러면 그 마지막 과정에서 나눈 수가 바로 최대공약수(GDC)인 것이다.

184 % 42 = 16
42 % 16 = 10
16 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0
GDC = 2

이러한 과정은 반복문과 재귀함수로 구현이 가능하다.

 

먼저 반복문을 이용한 최대공약수를 구하는 코드이다.

int GetGDC(int a, int b) //(a > b)
{
	int c = a % b;
	while (c != 0) //나머지가 0이 될 때 반복문 탈출.
	{
		a = b;
		b = c;
		c = a % b;             
	}
	return b;
}

while문을 진입 한 후 마지막 줄에 c의 값이 0이 되면, 다음 반복문으로 넘어갈 때 탈출을 하게 된다.

그리하여 나머지가 0이 될 때의 b값을 구할 수 있게 된다.

 

다음으로 재귀함수를 이용한 최대공약수를 구하는 코드이다.

int GetGDC(int a, int b)  //(a > b)
{
	if (b == 0) // a % b를 나눈 나머지가 0이면, a값을 반환.
	{
		return a;
	}
	else  //그렇지 않으면, 재귀함수 호출.
	{
		return GetGDC(b, a % b);
	}
}