유클리드 알고리즘

유클리드 알고리즘

두 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 방법이다.

 

기본 원리는 두 수의 최대공약수는, 두 수의 모듈러 값과 작은 숫자의 최대 공약수와 같다는 성질을 반복적으로 이용해 계산한다.

int GCD()
{
	int a = 48;
	int b = 30;

	while (b != 0)
	{
		int temp = b;
		b = a % b;
		a = temp;
	}

	return a;
}