[백준1934] 최소공배수

문제

---

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

풀이

---

방법1) 유클리드 호제법을 이용하여 gcd를 구한 뒤 lcm = A*B//gcd를 이용

방법2) 마찬가지로 유클리드 호제법을 이용해 gcd를 구하지만 lcm = gcd * (a//gcd) * (b//gcd)를 이용

코드

---

방법1)  lcm = A*B//gcd 이용

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    #기존의 값을 복사해둠
    x = a
    y = b
    # a, b 중 뭐가 큰지 나누지 않아도 노상관
    # Ex) gcd(18,24)=gcd(24,18)처럼 되므로 
    while b != 0:
        r = a % b
        a = b
        b = r
    gcd = a
    lcd = x * y // a
    print(lcd)

 

방법2)  lcm = gcd * (a//gcd) * (b//gcd) 이용

def gcd(a,b):

    if a==0:
        return b
    elif b==0:
        return a

    if a>b:
        a %= b
        return gcd(a,b)
    else:
        b %= a
        return gcd(a,b)
        
if __name__ == '__main__':
    trial = int(input())
    for i in range(trial):
        a, b = map(int, input().split())
        result = gcd(a,b)
        result *= (a//result) * (b//result)
        print(result)