[Algorithm/Python(파이썬)] 유클리드 호제법(Euclidean algorithm)

유클리드 호제법(Euclidean algorithm)

2개의 자연수의 최대공약수를 구하는 알고리즘

비교대상의 두 개의 자연수 n, m (단 n >m)에서 n을 m으로 나눈 나머지를 r이라고 했을때 GCD(n, m) = GCD(m, r)과 같고 r이 0이면 그때 m이 최대공약수이다. 라는 원리를 활용한 알고리즘

 

 

GCD (Greatest Common Divisior) - 최대공약수

두 수 혹은 그 이상의 여러 수의 공통인 약수 중 최대 인 수

 

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

8의 약수 : 1, 2, 4, 8

8과 12의 최대 공약수  : 4

 

# 유클리드 호제법을 이용한 최대 공약수를 구하는 파이썬 코드
def gcd(n, m):
    while (n > 0):
        m,n = n, m % n
    return m

 

 

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

두 수, 혹은 그 이상의 수들의 공통인 배수 중에서 가장 작은 수 

 

12의 배수 : 12, 24, 36, 48, 60

8의 배수 : 8, 16, 24, 32, 40, 48

8과 12의 최소 공배수  : 24

 

n * m = xyG^2

-> xyG = 최소공배수

 

LCM = n * m /  최대공약수 = n * m / gcd(n, m)

# 최소 공배수를 구하는 파이썬 코드
def lcm(n,m):
    return int(n*m / gcd(n, m))

 

---

위 설명들은 유클리드 호제법을 이용해 알고리즘을 직접 구현하는 방법이고 파이썬에는 Math 함수를 통해 간단하게 구할 수 있다. 

 

• math.gcd() - 최대공약수

import math

print(math.gcd(2, 5))

# 출력 1

 

 

• math.lcm() - 최소공배수

import math

print(math.gcd(2, 5))

# 출력 10

python 3.7 버전에서는 lcm은 error가 난다. 

 

찾아보니 math.lcm은 파이썬 3.9부터 사용 가능하다고 한다.