[백준] 2609번 : 최대공약수와 최소공배수 (Python)

문제 : https://www.acmicpc.net/problem/2609

 

 

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램이다.

 

import sys

input = sys.stdin.readline

# 유클리드 호제법으로 구하는 최대공약수
def gcd(N, M): 
    
    if(M == 0):
        return N
    
    return gcd(M, N%M)

N, M = map(int, input().split())

g = gcd(N, M)
lcm = (N*M) // g # 최소공배수

print(g)
print(lcm)

 

 

- 최대공약수 : 유클리드 호제법으로 구하기

- 최소공배수 : N과 M을 곱해 최대공약수로 나눠주면 최소공배수가 된다.