[Algo] 유클리드 호제법 (최대공약수, 최소공배수 구하기)

유클리드 호제법/알고리즘

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나
• 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

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

 

최대공약수 구하기

• 유클리드 호제법을 이용해 두 수 a, b의 최대공약수를 구할 수 있다.

/* get_gcd: parameter로 주어지는 두 수 a, b의 최대공약수를 구하는 함수 (a > b) */
int get_gcd(int a, int b) {
	int r = a % b;
	if (r == 0) return b;
	return get_gcd(b, r);
}

 

최소공배수 구하기

• 최대공약수를 이용해 최소공배수를 구할 수 있다.
• gcd를 두 수 a, b의 최대공약수라고 했을 때, a, b의 최소공배수는 a * b / gcd 이다.

/* get_gcd: parameter로 주어지는 두 수 a, b의 최대공약수를 구하는 함수 (a > b) */
int get_gcd(int a, int b) {
	int r = a % b;
	if (r == 0) return b;
	return get_gcd(b, r);
}

/* get_lcm: parameter로 주어지는 두 수 a, b의 최소공배수를 구하는 함수 */
int get_lcm(int a, int b) {
	int gcd = (a >= b) ? get_gcd(a, b) : get_gcd(b, a);
	return a * b / gcd;
}