[백준] #2609 최대공약수와 최소공배수(python)

📌문제

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

입력

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

출력

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

예제 입력

24 18

예제 출력

6
72

백준 2609번 문제

💡Idea

최대공약수란, 주어진 두 수 이상의 공약수들 중 가장 큰 수를 의미한다.
최소공배수란, 주어진 두 수 이상의 공배수들 중 가장 작은 수를 의미한다.

최대공약수와 최소공배수의 개념과, 계산하는 방법을 사용하여 구현해보았습니다.

최대공약수의 경우, 두 수를 동시에 나누는 수 중 가장 큰 수로 구현하고, 최소공배수의 경우, 아래 식에 따라 계산하였습니다.

$M, N$의 최대공약수를 $i$라고 할 때, 최소공배수는 ${M \over i} \times {N \over i}\times i = {MN \over i}$

💻코드1

import sys
M, N = map(int, sys.stdin.readline().split())

for i in range(min(M, N), 0, -1):
    if M % i == 0 and N % i == 0:
        print(i)
        print(M * N // i)
        break

📝코드 설명1

변수

• M, N : 주어진 두 수

주어진 두 수 중 더 작은 수부터 나누어가며, 두 수를 모두 나누는 가장 큰 수를 찾습니다.
최대공약수를 찾으면, 최대공약수를 이용하여 최소공배수를 찾아냅니다.

💻코드2

import sys
M, N = map(int, sys.stdin.readline().split())
def GCD(m, n):
    return GCD(n, m % n) if n else m

gcd = GCD(M,N)
print(gcd)
print(M * N // gcd)

📝코드 설명2

최대공약수를 구하는 알고리즘인 유클리드 호제법을 활용하여 코드를 작성할 수도 있습니다.

유클리드 호제법에 대해서 알고 싶다면?🧐

💻코드3

파이썬 3.9버전 이상이라면, 최대공약수와 최소공배수를 구할 수 있는 내장 함수가 추가되었습니다.

해당 함수들을 사용하여 간단하게 최대공약수와 최소공배수를 구할 수 있습니다.

import math
import sys
M, N = map(int, sys.stdin.readline().split())
print(math.gcd(M, N))
print(math.lcm(M, N))

⏰시간과 메모리

유클리드 호제법을 사용하지 않았을 때(코드 1)

• 메모리 : 30840 KB
• 시간 : 84 ms

유클리드 호제법을 사용했을 때(코드 2)

• 메모리 : 30840 KB
• 시간 : 72 ms

math 모듈 사용 시(코드 3)

• 메모리 : 32952 KB
  시간 : 72 ms