[파이썬] 최소 공배수, 최대 공약수 구하기

완전 탐색 활용

• 최대 공약수(GCD) : O(N)의 시간 복잡도
• 최소 공배수(LCM) : O(N*M)의 시간 복잡도

n, m = map(int, input().split())

# 최대 공약수
for i in range(max(n, m), 0, -1):
    if n % i == 0 and m % i == 0:
        print(i)
        break
# 최소 공배수
for i in range(min(n, m), n * m + 1):
    if i % n == 0 and i % m == 0:
        print(i)
        break

유클리드 호제법 : 최대 공약수를 빠르게!

• 유클리드 호제법을 사용하면 최대 공약수를 재귀적으로 구할 수 있다.
• 이 경우 최대 공약수를 구하기 위해 필요한 시간 복잡도는 O(logN)이다.
• 유클리드 호제법은 다음과 같다.

두 양의 정수 $a, b(a>b)$ 에 대하여 $a=b q+r(0 \leq r<b)$ 이라 하면, $a, b$ 의 최대공약수는 $b, r$ 의 최대공약수와 같다.
따라서 $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, r)$이고 $r=0$ 이라면, $a, b$ 의 최대공약수는 $b$ 가 된다.

\[a = bq_1 + r_1(0<r_1<b)\]

\[b = r_1q_2 + r_2(0<r_2<r_1)\]

\[r_1 = r_2q_3 + r_3(0<r_3<r_2)\]

$$\vdots$$

$$r_{n-2} = r_{n-1}q_n + r_n(0 < r_n < r_{n-1})$$

$$r_{n-1} = r_{n}q_{n + 1}$$

$$\therefore  gcd(a, b) = r_n$$

 

유클리드 호제법을 파이썬 코드로 구현하면 다음과 같다.

• 반복문

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

• 재귀문

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

---

최소 공배수 구하기 : 최대 공약수와의 관계를 활용

• 최소 공배수는 최대 공약수와의 관계를 통해서도 계산할 수 있다.
• 따라서 앞서 유클리드 호제법으로 계산한 최대 공약수를 활용하여, 빠르게 최소 공배수를 구하도록 하자. 

https://jwj4519.com/entry/최대공약수와-최소공배수의-관계-중등수학

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

---

참고

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