문제

문제1) 최대공약수와 최소공배수 (중등1, 고등1)

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

입력

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

입력 예시

24 18

출력

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

출력 예시

6
72

문제 풀이

이전에 풀었던 최대공약수를 구하는 방법은 그대로 사용하고,
최소 공배수에 대해서 추가로 코드를 작성하였다.

최소 공배수를 구하는 방법은 아래와 같다.

최소 공배수 = (a X b) / (두 수의 최대 공약수)

이를 이용해서 문제를 풀게 되면 다음과 같다.

a,b = map(int, input().split(" "))

# 최대공약수
def GCD(a,b):
    while b != 0:
        a, b = b, a%b
    return a

# 최소공배수 : 두 수를 곱하고 최대공약수로 나누기
def LCM(a,b):
    return int((a*b)/GCD(a,b))

print(GCD(a,b))
print(LCM(a,b))

cf ) python에는 최대공약수와 최소공배수를 구할 수 있는 내장 함수가 있다.
이를 이용해서 풀면 더 쉽게 풀 수 있다.

# https://codeup.kr/problem.php?id=4506

from math import gcd, lcm

a,b = map(int, input().split(" "))

print(gcd(a,b))
print(lcm(a,b))

최근에 문제를 풀면서 갑자기 수학에 대한 지식이 늘어나는 것 같다.
기억도 안나는 유클리드 호제법을 떠올리게 되었고 최대공약수와 최소공배수를 구하는 방법까지 알게되었다. :)