백준 1934 풀이 (최소공배수, 유클리드 호제법)

저번 2609문제에서 최대공약수와 최소공배수를 구했다. 이번에는 최소 공배수만 구하는 문제이기 때문에 저번에 사용했던 코드를 재활용해주면 아주 쉽게 구할 수 있다.

최소 공배수를 노가다로 구하게 되면 불필요한 연산이 너무 많아진다.

따라서 최대 공약수를 유클리드 호제법으로 구하고

이후에 최소 공배수를 구하는 방식이 효율적이다.

따라서 저번에 활용한 코드를 재활용하는 것이다. 그냥 함수로 묶어 주기만 하면 된다.

n = int(input())

def find(tmp):
    if tmp[0] < tmp[1]:
        t = tmp[0]
        tmp[0] = tmp[1]
        tmp[1] = t
    a = tmp[0]
    b = tmp[1]
    # get 공약수
    yak = 0
    while 1:
        c = tmp[0] % tmp[1]
        tmp[0] = tmp[1] 
        tmp[1] = c
        if tmp[1] == 0:
            break
    yak = tmp[0]
    if yak == 1:
        be = a*b
        print(be)
    else:
        a = a // yak
        b = b // yak
        print(yak * a * b)    

for _ in range(n):
    tmp = list(map(int, input().split()))
    find(tmp)