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

---

# 답

 

math 라이브러리를 사용하지 않은 풀이

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 a * b // gcd(a, b)

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

 

math 라이브러리를 사용한 풀이

import math

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

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

 

 

 

 

---

# 유클리드 호제법

 

 

2개의 자연수 a, b에 대하여, a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.