백준 2609번 최대공약수와 최소공배수 파이썬

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

2609번: 최대공약수와 최소공배수

 

답안

def gcd(m, n): # 최대공약수 함수
    if n == 0:
        return m
    return gcd(n,m%n)
    
m, n = map(int, input().split())

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

 

---

 

이산 수학을 공부하면서도 배웠지만 최소공약수 구하는 것은 유클리드 호제법을 참고하여 알고리즘을 짜면 된다.

방법은 여러 가지로 볼 수 있지만 나는 유클리드 호제법을 사용하여 문제를 풀었다.

옛날에는 이렇게 푼 적도 있다.

 

m, n = map(int, input().split())
a = min(m,n)
b = max(m,n)
for i in range(a, 0, -1): # GCD
    if (m % i) == 0 and (n % i) == 0:
        print(i)
        break
cnt = 1
while True:
    lcm = cnt * a
    if lcm % b == 0:
        print(lcm)
        break
    else:
        cnt += 1

 

또는 파이썬 라이브러리를 사용하여 풀어도 된다.

 

import math

m, n = map(int, input().split())
print(math.gcd(m,n))
print(m*n//math.gcd(m,n))

 

라이브러리를 사용하는 게 더 좋지만 알고리즘을 연습할 때는 위의 코드처럼 하는 게 공부에 도움이 더 잘 되는 것 같다.