[C++] 유클리드 호제법 (최대 공약수 & 최대 공배수)

 

 

 

이 포스터에선 유클리드 호제법에 대해 알아보도록 하겠다.

유클리드 호제법은 두 수 A와 B에 대해 최대 공약수를 구할 때 사용된다.

앞으로 A와 B의 최대 공약수는 GCD(A, B)로 가정하겠다.

 

GCD(A, B) 수학적 정의

2개의 자연수  A, B에 대해서 A를 B로 나눈 나머지를 r이라 하면 (단 A > B), A와 B의 최대공약수는 B와 r의 최대공약수와 같다. 이 성질에 따라, B를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수이다.

 

 

 

GCD(A, B) 코드 정의

A % B == 0이면 B를 가지고, A % B != 0이면 GCD(B, A % B)를 수행한다.

즉, 나머지가 0이 될 때의 B가 최대 공약수가 된다.

 

 

 

 

 

최대 공약수(GCD) 구하기

 

최대 공약수는 GCD(A, B) 자체이기 때문에 간단하다.

시간 복잡도는 O(log N)으로 매우 짧다.

(Naive 알고리즘을 사용하면 O(N)이 거린다.)

 

 

GCD 코드

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

 

 

 

 

 

최소 공배수(LCM) 구하기

최소 공배수(LCM) =  A * B / 최소 공약수(GCD)

위 공식을 따른다.

 

 

 

LCM 코드

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}