[Python] 최대공약수와 최소공배수 - 유클리드 호제법

유클리드 호제법

최대공약수 구하기

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

 

예시

a=72, b=30일 때, 최대공약수는 6이다.

30과 a를 b로 나눈 나머지인 12의 최대공약수도 6이다.

12와 (30%12=) 6의 최대공약수도 6이다.

 

💡 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 💡

a	b	a % b
72	30	12
30	12	6
12	6	0

👉 12 % 6 = 0이기 때문에 나누는 수인 6이 a와 b의 최대공약수 이다.

 

최소공배수 구하기

최소공배수 L = 최대공약수 G * a * b 이다.

a는 A를 G로 나눈 몫이다. 따라서 A 는 G * a이다.

마찬가지로 b = G * b 이다.

 

L = G * a * b 에서

→ G * a = A 이기 때문에, L = A * b 와 같고

→ G * b = B 이므로 L * G = A * (G * b) 이다

→ 따라서 L * G = A * B 이다.

 

그렇다면 최소공배수 L은 다음과 같은 식으로 구할 수 있다.

✔️ L = (A * B) / G

 

코드

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

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

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(lcd(a, b))

: 입력한 a, b에 대한 최소공배수를 구하는 알고리즘

---

알고리즘 풀 때마다 긴가민가 하길래 결국 포스트로 정리하기...

 

참고 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전