백준 22.03.17. 1934번 - 최소공배수

 

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

유클리드 호제법은 최대공약수를 구할 때 사용되는 방법이며 큰 수(A)를 작은 수(B)로 나누어 그 나머지를 이용하여 최대공약수를 구하는 방법입니다

---

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


T = int(input())

for i in range(T):
    A, B = map(int, input().split())
    div = gcd(A, B)
    print(A*B//div)

• 유클리드 호제법으로 작성한 함수를 사용합니다.
• 입력받은 수 A, B의 최대공약수가 div일 때, A = a * div, B = b * div 가 됩니다.
• 따라서 최소공배수는 A * B / div = (a * div) * (b * div) / div = a * b * div 가 됩니다.