[알고리즘] 최대공약수, 최소공배수 (유클리드 호제법)

최대공약수(greatest common divisor(factor), GCD),  최소공배수(least common multiple, LCM)를 구하는 방법에 대해 알아보자.

 

최대공약수, 최소공배수란?

최대공약수(GCD) : 두 수 혹은 여러 수의 공통인 약수 중 가장 큰 것

최소공배수(LCM) : 두 수 혹은 여러 수의 공통인 배수 중 가장 작은 것

 

 

최대공약수, 최소공배수 구하기

최대공약수를 구하는 방법에는 다음과 같이 계속 나누는 방법도 있다.

ex.

2 | 72 56
2 | 36 28
2 | 18 14
    -----
    9  7

따라서 72와 56의 최대공약수는 2*2*2 = 8이므로 8이고, 최소공배수는 2*2*2*9*7 = 504이므로 504이다.

 

하지만 이런 방법의 시간 복잡도는 O(N)이므로 시간복잡도가 O(logN)인 유클리드 호제법을 사용할 필요가 있다.

 

유클리드 호제법

유클리드 호제법은 최대공약수를 구하는 방법이다.

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

gcd(a, b) = gcd(b, r)
a와 b의 최대공약수 = b와 r의 최대공약수

r이 0이라면, a, b의 최대공약수는 b이다.

 

따라서, 다음과 같이 최대공약수를 구할 수 있다.

ex.

72 % 56 = 16
56 % 16 = 8
16 % 8  = 0

따라서 72와 56의 최대공약수는 16 % 8 = 0이므로 8이고, 최소공배수는 두 수의 곱에 최대공약수를 나누면 되고, 72*56/8 = 504이므로 504이다.

 

증명

두 수의 최대공약수

1. gcd(a, b)
1-1. a와 b의 최대공약수를 d라고 가정하자. (a > b)
1-2. a = αd, b = βd 라고 할 수 있다.
1-3. 더 이상 공약수가 없어야 하므로 α, β는 서로소이다.
1-4. a > b이므로 a = bn + r (0≤r<b)
1-5. 1-2번을 이용하면, 1-4번을 αd = βdn + r 이라고 나타낼 수 있다.
1-6. 1-5번을 통해, r은 d의 배수임을 알 수 있으므로 r = qd로 나타낼 수 있다.

2. gcd(b, r)
2-1. β와 q가 서로소가 아니라고 가정하자. 
2-2. 즉, β = β'd', q = q'd' 일때 d' > 1 이라고 가정하자. (β', q' 는 서로소)
2-3. b = β'd'd, r = q'd'd 라고 할 수 있다.
2-4. 1-2번과 2-3번을 이용하면, 1-3번을 αd = β'd'dn + q'd'd 이라고 나타낼 수 있다.
2-5. 2-4번을 α = d'(β'n + q') 으로 정리할 수 있다.
2-6. 만약, d' > 1 이라면 α와 β는 서로소가 아니므로 모순이다.
2-7. 따라서 d' = 1 이 되야한다.
2-8. β와 q가 서로소이므로 b와 r의 최대공약수는 d이다.

 

∴ gcd(a, b) = gcd(b, r)

 

적용

이제 유클리드 호제법을 이용하여 백준 1934번: 최소공배수 문제를 풀어보자.

문제

첫 줄에는 테스트 개수 t가, 그 다음 줄부터는 최소공배수를 구하고 싶은 두 수 a, b를 t만큼 입력받고 최소공배수를 출력한다.

풀이

최소공배수는 구하고자 하는 두 수를 곱한뒤 최대공약수를 나누어 계산한다. 

최대공약수는 유클리드 호제법을 이용하여 구해준다. a와 b를 매개변수로 받는 함수를 만들고, b가 0일때 최대공약수가 a인 성질을 이용한다.

b가 0이 아니라면 a에 b를 b에 a%b를 매개변수로 갖는 함수를 b가 0이 될 때까지 계속해서 호출한다.

import sys


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

t = int(sys.stdin.readline())

for i in range(t):
    a, b = map(int, sys.stdin.readline().split())
    
    if a < b: a, b = b, a    	  #a % b = r일때 무조건 a > b 여야함.
    print(int(a*b/gcd(a,b)))      #최소공배수

 

 

 

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

1934번: 최소공배수