유클리드 호제법(Euclidean algorithm)은 두 정수의 최대 공약수를 구하기 위한 알고리즘이다.
왜 공식이 아니라 알고리즘인가 했는데, 값을 구하기 위해 정해진 규칙에 따라 단계의 절차를 밟아 계산을 진행하기 때문에 그렇다고 한다. 기원전 300 원경에 나와서 지금까지 쓰이는 중이다.
이후 나올 약어들만 정리하고 가자면:
- \(GCD\): Greatest Common Divisor. 최대공약수
- \(LCM\): Least Common Multiple. 최소공배수
유클리드 호제법: 최대공약수 계산
유클리드 호제법이 성립하기 위한 정리는 다음과 같다.
2개의 자연수 \(A, B\) 에 대해 \(A\)를 \(B\)로 나눈 나머지를 \(R\)이라 하자. \((A \geq B, 0 \leq R < B)\)
이때, \(A\)와 \(B\)의 최대공약수는 \(B\)와 \(R\)의 최대공약수와 같다.
위 정리를 활용해 최대공약수를 계산하기 위한 알고리즘은 아래 순서를 따른다.
- \(A\)를 \(B\)로 나눈 나머지 \(R\)을 구한다.
- \(R\)이 \(0\)이라면, \(B\)가 최대공약수이다. 알고리즘을 종료한다.
- \(R\)이 \(0\)이 아니라면, \(A\) 자리에 \(B\), \(B\) 자리에 \(R\)을 넣고 1번으로 돌아가 알고리즘을 반복한다.
최대공약수 계산 구현 코드 (Java)
반복문 또는 재귀 함수를 사용해 구현할 수 있다.
반복문 구현
public static int gcd(int a, int b) {
int r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}재귀 함수 구현
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
최소공배수 계산
2개의 자연수 \(A, B\)에 대해 \(A\)와 \(B\)의 최소공배수는 두 수의 곱을 최대공약수로 나눈 것과 같다. 식으로 표현하면 다음과 같다.
\(A * B = GCD(A, B) * LCM(A, B)\)
\(LCM(A, B) = A * B / GCD(A,B)\)
최소공배수 계산 구현 코드 (Java)
위에서 구현한 gcd 메서드를 활용해 구현하면 된다.
public static int lcm(int a, int b) {
return a / gcd (a, b) * b; // int overflow 방지 위해 a를 gcd(a,b)로 나눈 후 b를 곱함
}
