[Python] 유클리드 호제법으로 최대 공약수, 최소 공배수 구하기

사실 파이썬을 사용하면 유클리드 호제법 없이 math 라이브러리를 사용하여 빠르게 최대공약수와 최소공배수를 구할 수 있다.

 

✅ math 라이브러리 사용

import math

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

print(math.gcm(a, b)) # 최대공약수 출력
print(math.lcm(a,b)) # 최소공배수 출력

 

 

✅ 용어 정리

✔ GCD (Greate Common Divisor) - 최대 공약수

4의 약수: 1, 2, 4

24의 약수: 1, 2, 3, 4, 6, 8, 12, 24

 

4와 12의 공약수: 1, 2, 4 (공약수 중에서 가장 큰 수)

최대 공약수: 4

 

✔ LCM (Largest Common Multiple) - 최소 공배수

3의 배수: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30

5의 배수: 5, 10, 15, 20, 25, 30, 35, 40, 45

 

3과 5의 공배수: 15, 30, 45 (공배수 중에서 가장 작은 수)

최소 공배수: 15

 

 

✅ 유클리드 호제법

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

 a와 b의 최대 공약수 == b와 r의 최대공약수
 GDC(a, b) = GCD(b, r) 과 같고 r이 0이면 그때의 m이 최대공약수이다.

 

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

 

 

 

✅ 코드

def gcd(a, b):
	while b > 0:
    		a, b = b, a % b
        return a

def lcm(a, b):
	return a * b // gcd(a, b)

 

 

 

 

 

✅ 참고 자료

https://donggyu.tistory.com/128

[Python 유클리드 호제법] 최대 공약수, 최대 공배수 구하기

https://codingpractices.tistory.com/entry/Python-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EB%9E%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

[Python] 최소공배수, 최대공약수란? 파이썬 알고리즘으로 쉽게 구현하기 / for문, 유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전