유클리드 호제법(Euclidean-Algorithm) feat. Python

유클리드 호제법이란? (최대공약수 구하기)

유클리드 호제법 또는 유크리드 알고리즘은 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘의 하나이다.

호제법이란 두 수가 서로 상대방 수를 나누어 결국 원하는수를 얻는 알고리즘을 나타낸다.

 

예시

* mod란 나머지 연산을 의미한다.

 

1071, 1029의 최대공약수

1) 1071은 1029로 나누어 떨어지지 않기 때문에 1071 mod 1029를 계산한다. => 42

2) 1029는 42로 나누어 떨어지지 않기 때문에 1029 mod 42를 계산한다. => 21

3) 42는 21로 나누어떨어진다. => 최대공약수: 21

 

24와 18의 최대공약수

1) 24와 18은 나누어 떨어지지 않기 때문에 24 mod 18을 계산한다. => 6

2) 18은 6으로 나누어떨어진다. => 최대공약수: 6

 

최소공배수 구하기

주어진 값 a와 b를 곱한 값을 최대공약수로 나누면 최소공배수가 나온다.

 

24와 18의 최소공배수

24 * 18 // 6(최대공약수) = 72

 

파이썬 코드

아래와 같은 방식으로 최대공약수, 최소공배수를 구할 수 있다.

def GCD(a,b):
    while b:
        a,b = a%b
    return a

def LCM(a,b):
    ans = (a*b) // GCD(a,b)
    return ans

 

또한 파이썬에는 math 함수를 사용하면 최대공약수와 최소공배수를 매우 쉽게 구할 수 있다.

import math

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

(참고) math.lcm은 파이썬 3.9 버전부터 사용할 수 있다! 3.5~ 3.8 버전에서는 오류가 날 것이다.