Math_10_LCM(5347)

문제

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

풀이

• 이전에 구현해 보았다.
• 1. LCM 라이브러리 사용법
• 2. 유클리드 호제법 이용법(큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다.)

최대 공약수

예를 들어, 20과 12의 최대 공약수를 구한다고 가정하자. 과정은 다음과 같다.
20 / 12 를 해준다. 나머지는 8이다.
12 / 8 을 해준다. 나머지는 4이다.
8 / 4 를 해준다. 나머지는 0이다.
나머지가 0이니 4가 20과 12의 최대 공약수이다.

최소 공배수

두 수의 최소 공배수 (Least Common Multiple, LCM) 를 구하기 위해선 
두 수의 곱을 최대 공약수로 나눠주기만 하면 된다. 

코드

import sys
sys.stdin = open("input.txt","rt")
from math import lcm    
def input():
    return sys.stdin.readline().rstrip()


N = int(input())

# 큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 


def gcd(a, b): # 최대공약수
    a, b = max(a, b), min(a, b)
    while b != 0:
        a,b = b, a % b
    return a
def lcm(a, b): # 최소공배수
  return int(a * b / gcd(a, b))



for i in range(N):
    
    a, b = map(int,input().split())

    print(lcm(a,b))

배운 것

코멘트