[알고리즘][Python] 백준(BOJ) 5347 LCM_파이썬

 

5347 LCM    www.acmicpc.net/problem/5347

5347번: LCM

 

 

 

문제 풀기 전 공부할 것 : 수학, 정수론 유클리드 호제법

 

 

 

 

 

 

 

풀이

<내용>

• a와 b의 최소 공배수를 구하는 방법은 a와 b를 곱하고 a와 b의 최대 공약수를 나누는 방법이 있다.
• 따라서 최대 공약수를 구하는 gcd 함수를 정의한다.
  • 유클리드 호제법을 이용한다.
• 그리고 최소 공배수를 구한다.

 

 

<코드>

import sys
input = sys.stdin.readline

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

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(a*b//gcd(a, b))