Post

[Algorithm] 유클리드 호제법(Euclidean Algorithm): 최대공약수(GCD)와 최소공배수(LCM) 구하기

Posted Updated
By Seungri
5 min read
[Algorithm] 유클리드 호제법(Euclidean Algorithm): 최대공약수(GCD)와 최소공배수(LCM) 구하기

유클리드 호제법(Euclidean Algorithm)

유클리드 호제법이란, 두 개의 양의 정수에 대해 최대공약수(GCD, greatest common divisor)를 구하는 알고리즘이다.

“호제법”이라는 것은 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 의미한다.


유클리드 호제법의 내용을 간단히 정리하면 다음과 같다.

두 양의 정수 \(a, b \space (a>b)\)에 대하여 \(a=b \cdot t+r\) \((0\le r<b)\), 즉 \(r =a\mod b\) 라고 하자. 이때,

  • \(r=0\)이라면, \(\gcd (a, b)=b\)이다.

  • 그렇지 않다면, \(\gcd(a, b)=\gcd(b, r)\)이다.


이러한 유클리드 호제법을 이용하여 두 양의 정수의 최대공약수와 최소공배수를 구할 수 있다. 각 방법을 알아보기 전에, 어떻게 유클리드 호제법을 증명할 수 있는지 살펴보자.


증명

\(r=a \mod b\)이고 \(a=b\cdot t +r\)일때, \(\gcd(a, b)=\gcd(b, r)\) 임을 증명해보자.

  1. 우선, \(d=\gcd(a,b)\)로 가정한다.

    기본 정의에 의해 \(a\)와 \(b\)는 모두 \(d\)로 나누어떨어지는데, \(a =b\cdot t+r\)이므로 \(r\) 또한 \(d\)로 나누어떨어지게 된다.

    즉, \(b\)와 \(r\)이 모두 \(d\)로 나누어떨어지므로, \(\gcd(b,r)\)은 \(\gcd(a, b)\)(== \(d\))로 나누어떨어진다.

  2. 이어서 \(c=\gcd(b, r)\)로 가정한다.

    기본 정의에 의해 \(b\)와 \(r\)은 모두 \(c\)로 나누어떨어지는데, \(a=b\cdot t+r\)이므로 \(a\) 또한 \(c\)로 나누어떨어지게 된다.

    즉, \(a\)와 \(b\)가 모두 \(c\)로 나누어떨어지므로, \(\gcd(a,b)\)는 \(\gcd(b,r)\)(== \(c\))로 나누어떨어진다.


이를 모두 종합해보면 \(\gcd(a,b)\)와 \(\gcd(b,r)\)이 서로의 값으로 나누어떨어지기 때문에, \(\gcd(a,b)=\gcd(b,r)\) 임을 확인할 수 있다.


최대공약수(GCD) 구하기 (in Python)

개념적으로 접근하면 다음과 같이 재귀적으로 함수를 작성할 수 있다.

1
2
3
4
5

def gcd(a, b):
    if (r := a % b) == 0:
        return b
    else:
        return gcd(b, r)


이를 반복문(w/ 파이썬 다중 할당)으로 바꾸면 다음과 같다.

1
2
3
4

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


또한, 시간 복잡도는 \(O(\log(\min(a,b)))\)이다. 이에 대한 자세한 유도 과정은 링크1, 링크2를 참고한다.


이때, gcd(a, b) 함수에서 \(a\)와 \(b\)의 입력 순서가 꼭 \(a>b\)일 필요는 없다. 왜냐하면 \(a <b\)인 경우일지라도, 첫 나머지 \(r\)을 구하고 \(b\)와 \(r\)로 입력 값을 바꿈으로써 그 순서가 맞추어지게 되기 때문이다.

다음과 같이 입력 값의 순서를 바꾸어서 각 단계마다 값을 출력해보면 동작을 확인할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12

print(gcd(1071, 1029))
# a=1071 / b=1029
# a=1029 / b=42
# a=42 / b=21
# 21

print(gcd(1029, 1071))
# a=1029 / b=1071
# a=1071 / b=1029
# a=1029 / b=42
# a=42 / b=21
# 21


최소공배수(LCM) 구하기 (in Python)

두 양의 정수의 최소공배수(LCM, least common multiple)를 구하려면, 두 수를 곱한 값을 최대공약수로 나누면 된다.

두 양의 정수의 곱은 두 수의 최대공약수와 최소공배수의 곱으로 나타낼 수 있다.

\[a\times b=\gcd(a, b) \times \text{lcm}(a,b)\]


즉, 다음과 같은 순서로 로직을 작성할 수 있다.

  1. 유클리드 호제법을 통해 두 수의 최대공약수를 구한다.
  2. 두 수의 곱을 1번에서 구한 최대공약수로 나눈다.


1
2

def lcm(a, b):
    return a * b // gcd(a, b)


References

Problem Solving, Algorithm Snippet
algorithm python math gcd lcm
This post is licensed under CC BY 4.0 by the author.