[백준] 2609번 - 최대공약수와 최소공배수

📩 출처

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

👉 생각

• 일반적으로 두 수(m, n)의 최소 공배수를 구하는 방법은 (m*n) // 최대 공약수 이기 때문에, 최대 공약수를 구하는 코드만 생각하면 된다.
• 보통 최대 공약수를 구할 때 유클리드 호제법을 많이 사용한다.
• 유클리드 호제법이란, 두 개의 자연수 m과 n에서 (m > n) m을 n으로 나눈 나머지를 이용하는 방법이다.

  MOD 연산 : 두 값을 나눈 나머지를 구하는 연산

• 예를 들어 m = 48, n = 18 일때,

48 % 18 = 12

• 다음으로 이전에 나누어 주었던 수(18)와 나머지(12)로 MOD 연산을 진행한다.

18 % 12 = 6

• 이 과정을 계속 반복한다.

12 % 6 = 0

• 나머지가 0이 되었을 때 마지막 계산에서 나누는 수로 사용된 6이 48과 18의 최대공약수이다.

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

# 최대공약수
def gcd(m, n): 
    if n == 0:
        return m
    return gcd(n,m%n)
print(gcd(m, n))

# 최소공배수
print(int(m*n/gcd(m,n)))

• 위 코드 적용하기 전에 math 모듈 불러와서 일단 통과부터 했다..ㅋㅋ

from math import gcd
m, n = map(int, input().split())

print(gcd(m,n))
print((m*n)//gcd(m,n))