유클리드 호제법 : 최대공약수와 최소공배수
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
유클리드 호제법(Euclidean algorithm)은 2개의 자연수 또는 두 정식(整式)의 최대공약수를 구하는 알고리즘이다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
정식(整式)은 수학에서 문자와 숫자에 대해 덧셈, 뺄셈, 곱셈만을 사용해서 구성된 식을 의미한다. 우리가 흔히 접하는 다항식이 정식에 포함되고, 나눗셈을 포함하더라도 분모에 문자가 없는 경우는 정식에 포함되지만, 분모에 문자가 포함된 식(분수식)은 정식에서 제외된다고 한다.
이 알고리즘은 인류 최초의 알고리즘이라 한다.
두 양의 정수 a, b에 대하여 a = bq + r (0 ≤ r < b)로 나타낼 수 있을 때, a, b의 최대공약수는 b, r의 최대공약수와 같다.
즉, gcd(a, b) = gcd(b, r) 이다.
q는 a를 b로 나눈 몫이고, r은 a를 b로 나눈 나머지이다.
최대공약수 구하기
1071과 1029의 최대공약수를 구해보자.
- 1071을 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다 -> 42
- 1029를 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다 -> 21
- 42를 21로 나누어 떨어지기 때문에, 최대공약수는 21이다.
C++로 작성해보면,
1
2
3
4
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
매개변수로 b > a인 경우가 넘어가더라도 a % b는 a가 b보다 작을 때 a가 그대로 반환되므로, gcd(b, a)로 넘어가게 된다.
또는 아래처럼 while문을 이용해서 작성할 수도 있다.
1
2
3
4
5
6
7
8
9
10
int gcd(int a, int b)
{
int c;
while (b)
{
c = a % b;
a = b;
b = c;
}
}
`
최소공배수 구하기
코드로 먼저 보자.
1
2
3
4
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
a와 b를 곱한 후에 최대공약수로 나누면 최소공배수가 된다.
이유를 설명하기 위해, 두 수 a = 12, b = 18를 예시로 들어보자. 두 수를 소인수분해하면 다음과 같다.
- 12 = 2^2 * 3^1
- 18 = 2^1 * 3^2
최대공약수는 두 수의 공통된 소인수 중 지수가 가장 작은 것들을 선택한다.
- gcd(12, 18) = 2^1 * 3^1 = 6
최소공배수는 두 수의 모든 소인수 중 지수가 가장 큰 것들을 선택한다.
- lcm(12, 18) = 2^2 * 3^2 = 36
여기서 두 수 a와 b를 곱해버리면,
a * b = (2^2 * 3^1) * (2^1 * 3^2) = (2^1 * 3^1) * (2^2 * 3^2) = gcd(a, b) * lcm(a, b)
lcm(a, b) = a * b / gcd(a, b)이 된다.
참고