[백준] 2609 | 최대공약수와 최소공배수 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/2609

입력받은 두 수의 최대공약수와 최소공배수를 구하는 문제이다.

 

접근

유클리드 호제법을 사용하면 최대공약수와 최소공배수를 쉽게 구할 수 있다.

최대공약수를 먼저 구한 후, 최소공배수는 구한 최대공약수를 이용해 구했다.(n * m = 최대공약수 * 최소공배수 인 것을 활용했다.)

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

def euc(a, b):
    if b > a: a, b = b, a
    a = a % b
    if a == 0: return b
    else: return euc(b, a)
    
gcd = euc(n, m)
lcm = n * m // gcd

print(gcd)
print(lcm)