[기본 개념] 최대 공약수, 최대 공배수 - 유클리드 호제법

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

유클리드 호제법은 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 

작동 원리는 두 개의 자연수 a,b가 (a>b) 있다고 하고, a를 b로 나눈 나머지를 r라고 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r2를 구하고 r을 r2로 나눈 나머지 r3...를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.

간단하게 코드로 표현하면 이런 식이다.

def greatest_common_divisor(n1, n2):
    while n2 != 0:
        n1, n2 = n2, n1 % n2
    return n1

 

최대 공약수는 이렇게 구할 수 있는데, 최소 공배수는 최대 공약수를 구하면 간단하게 구해진다. 

두 수 a,b가 있다고 할 때, 단순히 a와 b를 곱한다고 해서 최소 공배수가 만들어지지 않는다. 이유는 다들 알고 있겠지만, 두 수를 각각 인수분해를 진행했을 때 최대 공약수가 한번씩 더 곱해지는 것을 볼 수 있다. 

따라서 최소 공배수는 두 수를 곱하고 최대 공약수로 나눠주면 간단하게 구할 수 있다.

이걸 간단하게 살펴볼 예제를 가져왔는데, 백준 1934번 : 최소 공배수 문제다.

당연하게도 그냥 때려 브루트포스로 풀면 간단하게 풀린다. 그렇지만 시간 복잡도가 O(T * min(a,b))가 되어버린다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int,sys.stdin.readline().split())
    answer = 1
    for i in range(2, min(a,b)+1):
        while a % i == 0 and b % i == 0:
            answer *= i
            a, b = a//i, b//i
    answer *= a * b
    print(answer)

하지만 간단하게 둘을 곱한 다음 최대 공약수로 나눠주면, 간단하게 풀린다. 

import sys


def greatest_common_divisor(n1, n2):
    while n2 != 0:
        n1, n2 = n2, n1 % n2
    return n1


t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int,sys.stdin.readline().split())
    n = greatest_common_divisor(a,b)
    if n == 1:
        print(a * b)
    else:
        print(a*b//n)

밑이 시간 차이를 보여준다.