[백준 1934번] 파이썬 - 최소 공배수

백준 1934 - 최소 공배수

시간 제한 1초, 메모리 제한 128MB

# 조건

• 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다.
• 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
• 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.
• 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

• 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

# 접근 방법

• 유클리드 호제법을 이용하여 구하면 된다.
  • 유클리드 호제법이란 최대 공약수를 구할 때 유용하다.
  • 숫자 a, b가 있을 때 a를 b로 나눈 나머지와 b의 최대공약수는
  • a와 b의 최대 공약수와 같다.
  • • 따라서, a를 b로 계속 나누어서 b에 a로 나눈 나머지를 대입시켜서 b가 0이 될 때까지 반복을 하면, 남는 a의 값이 바로 최대 공약수이다.
• 최대 공약수를 구했다면 최소 공배수는 a와 b의 곱을 최대 공약수로 나누면 나오게 된다.
• 다만, python에서는 math 라이브러리의 gcd와 lcm을 이용하면 최소 공배수와 최대 공약수를 쉽게 구할 수 있다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def gcd(a, b):  
    while b > 0:  
        a, b = b, a % b  
    return a  

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

T = int(input())  
for _ in range(T):  
    a, b = map(int, input().split())  
    print(lcm(a, b))