유클리드 알고리즘: 최대공약수, 최소공배수 구하기

참고

• 「Rosen의 이산수학 8th Edition」 (Kenneth H. Rosen 지음)

 

내용 구성

1. 소인수분해 방식의 문제점
2. 유클리드 알고리즘이란?
3. 파이썬 코드
4. 관련 문제

---

최대공약수: gcd (greatest common divisor)
최소공배수: lcm (least common multiple)

 

1. 소인수분해 방식의 문제점

소인수분해로 GCD, LCM 구하기

소인수분해 방식은 일반적으로 많이 사용되지만, 비효율적인 방법이다. 두 정수가 커질수록 소인수분해를 구하는 데 시간이 오래 걸리기 때문이다.

 

 

 

2. 유클리드 알고리즘이란?

a = bq + r (a ＞ b)일 때, gcd(a, b) == gcd(b, r)라는 성질을 이용한다.

소인수분해 방식보다 더욱 효율적으로 최대공약수를 찾을 수 있는 알고리즘이다.

유클리드 알고리즘

위 그림은 유클리드 알고리즘으로 두 정수 a = 328과 b = 188의 최대공약수를 구하는 과정이다.

두 정수 중에서 더 큰 수인 a = 328을 작은 수인 b = 188로 나눈다. 나머지가 0이 아니므로, 더 큰 수 a는 188로 대체하고, 더 작은 수 b는 나머지로 대체한다. 즉, a = 188, b = 140 상태가 되는 것이다. 그럼 다시 188을 140으로 나누는데, 이러한 과정을 a % b == 0일 될 때까지 반복한다.

만약 a % b == 0이라면, 이때 b의 값이 최대공약수이다.

 

최소공배수

그럼 최소공배수는 어떻게 구할까? 처음의 두 정수 328과 188을 곱한 결과에 최대공약수를 나누어주면 된다.

일반적으로는 328과 188의 공통 약수로 나누다가, 더 이상 나누어지지 않을 때 공통 약수와 나누어지지 않는 두 수를 곱하여 최소공배수를 구한다. 위 그림에서 파란색 숫자들이 바로 최소공배수를 구하는 수이다. 그러나, 이 방법은 결국 기존 두 수에 최대공약수를 나누는 것과 동일함을 알 수 있다.

 

 

 

3. 파이썬 코드

def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
        print(a, b)
    return a

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

 

 

 

 

4. 관련 문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

백준에서 최대공약수와 최소공배수를 구하는 문제가 있다. 이미 위 파이썬 코드로 정답이 스포되었지만, 소인수분해 방식과 유클리드 알고리즘 방식으로 다양하게 풀어보면 좋을 듯하다.