유클리드 호제법 (최대공약수 구하는 알고리즘)

유클리드 호제법은 두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.

말로 설명하자면 다음과 같다.

두 양의 정수 $a,b (a>b)$에 대하여 $a = bq + r (0 ≤ r < b)$이라 하면, $a, b$의 최대공약수는 $b,r$의 최대공약수와 같다. 즉,
$gcd(a, b) = gcd(b, r)$
$r = 0$이라면, $a, b$의 최대공약수는 $b$가 된다.

파이썬 코드로 나타내면 다음과 같다.

# 최대공약수
def gcd(a, b):
    if b > a:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

$O((log N)^2)$의 시간복잡도로 최대공약수를 구할 수 있다.

추가로 최소공배수 구하는 법도 알아보자면 최소공배수는 최대공약수를 안다면 아주 쉽게 구할 수 있다.

두 수를 곱한 값을 최대공약수로 나누면 된다.

# 최소공배수
def lcm(a,b):
    return a * b // gcd(a, b)

파이썬의 math 라이브러리의 gcd, lcm 함수를 이용하면 최대공약수와 최소공배수를 더 쉽게 구할 수 있다. 이 함수들은 2개 이상의 인자를 넣어도 최대공약수, 최소공배수를 구할 수 있다.

• 최대공약수 : gcd()
  • 함수에 아무것도 인자로 넘겨주지 않거나 모든 인자가 0인 경우에는 0을 출력한다.
• 최소공배수 : lcm()
  • 함수에 아무것도 인자로 넘겨주지 않으면 1을 출력한다.
  • 모든 인자가 0인 경우에는 0을 출력한다.

import math

# 최대공약수
math.gcd()             # 0
math.gcd(0, 0, 0, 0)    # 0
math.gcd(2)        # 2
math.gcd(2, 8)        # 2
math.gcd(42, 56, 28)    # 14

# 최소공배수
print(math.lcm())        # 1
print(math.lcm(0, 0, 0, 0))    # 0
print(math.lcm(2))        # 2
print(math.lcm(2, 8))        # 8
print(math.lcm(42, 56, 28))    # 168

[참고]

유클리드 호제법-나무 위키