코딩테스트 준비
유클리드 호제법 - 최대공약수 구하는 알고리즘, 최소공배수
언어 수집가
2021. 2. 16. 13:38
def gcd(a, b):
while b > 0:
tmp = a
a = b
b = tmp % b
return a
최소공배수는 두 수를 곱한 뒤 최대공약수로 나눠서 구할 수 있다.
예를 들어 18과 24의 최대공약수는 6이고 각각 6x3, 6x4로 나타낼 수 있다. 최소공배수는 6x3x4이므로, 18과 24를 곱한 뒤 최대공약수로 한 번 나눠주면 된다.
def gcd(a, b):
while b > 0:
tmp = a
a = b
b = tmp % b
return a
최소공배수 = a*b // gcd(a, b)