#1 개념
유클리드 호제법은 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least Common Multiple)를 구하는 알고리즘으로, 고대 그리스 시대에 발견하여 O(log n)이라는 짧은 시간 복잡도를 가지고 있어 컴퓨터 프로그램에서 시간 복잡도를 줄이기 위한 알고리즘으로 많이 사용된다.
1-1. 원리
유클리드 호제법의 최대공약수 계산은 다음과 같은 원리에 기반한다.
- 두 수 a와 b의 최대공약수는 a와 b를 나눈 나머지의 최대공약수와 같다.
- 나머지 연산을 이용하여 계속해서 두 수의 나머지를 구하고, 나머지가 0이 될 때까지 반복한다.
- 마지막에 나누는 수가 두 수의 최대공약수이다.
유클리드 호제법의 최소공배수 계산은 다음과 같은 원리에 기반한다.
- 두 수 a와 b의 최대공약수를 d라고 한다.
- 최소공배수는 a와 b의 곱을 최대공약수로 나눈 값이다. 즉, a * b / d
1-2. 증명
두 수 A, B의 최대공약수 G라고 하자. a와 b가 서로소일 때, A, B는 아래와 같이 나타낼 수 있다.
A = G*a, B = G*b
이때 A와 B의 관계는 아래와 같이 정의할 수 있다.
A = Bq + R
나머지 R을 이항하여 정리하면 아래와 같다.
R = Bq + A = G*a - G*b*q = G*(a - bq)
따라서 세 수 A, B, C는 a, b, (a-bq)가 서로소이면 G를 최대공약수로 갖는다.
b와 (a-bq)가 서로소가 아니라면 k와 k'가 소로소일 때 공약수 m이 존재한다.
b = mk
a - bq = mk'
a = bq + mk'
= mkq + mk'
= m(kq + k')
b = mk
a와 b는 최대공약수 m을 갖게 된다.
m이 1이 아니면, 2이상의 공약수를 갖게 되어 a와 b가 서로소가 아니다.
m이 1이면, 공약수가 1이므로 b와 a-bq가 k와 k'로 서로소가 된다.
1-3. 예시
다음은 48과 18의 최대공약수를 유클리드 호제를 통해 계산하는 예시이다.
- 48을 18로 나눈 나머지는 12이다. (48 % 12 = 12)
- 18을 12로 나눈 나머지는 6이다. (18 % 12 = 6)
- 12를 6으로 나눈 나머지는 0이다. (12 % 6 = 0)
따라서 최대공약수는 6이다.
다음은 48과 18의 최소공배수를 유클리드 호제를 통해 계산하는 예시이다.
- 48과 18의 최대공약수는 6이다. (GCD(48, 18) = 6)
- 48과 18의 최소공배수는 144이다. (48 * 18 / 6 = 144)
따라서 최소공배수는 144이다.
#2 예제 코드
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int num1, num2;
cin >> num1 >> num2;
cout << "두 수의 최대공약수 = " << gcd(num1, num2) << endl;
cout << "두 수의 최소공배수 = " << lcm(num1, num2) << endl;
return 0;
}