유클리드 호제법 (Euclidean algorithm)

유클리드 호제법

2개의 자연수 또는 정수의 최대공약수 를 구하는 알고리즘의 하나이다.
호제법 이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.

 

2개의 자연수 a, b 가 있다고 했을 때 a 를 b 로 나눈 나머지 를 r 이라고 하면 (단, a>b )
a 와 b 의 최대공약수 는 b 와 r 의 최대공약수 와 같다.

 

b 를 r 로 나눈 나머지 를 r’ → r 을 r’ 로 나눈 나머지
위의 과정을 반복해서 나머지가 0이 되었을 때의 수가 a 와 b 의 최대공약수 이다.

 

 

 

이런 과정을 거쳐 다음 정리를 이용해서 유클리드 호제법 이 성립하게 된다.

정리

a, b 는 정수, a 를 b 로 나눈 나머지가 r 이라고 하자. ( a ≥ b , r은 0 ≤ r < b 인 정수)
a 와 b 의 최대공약수 를 (a, b) 라고 하면 (a, b) = (b, r) 의 공식이 성립.
이러한 공식을 파이썬을 사용해서 적용해보면 다음과 같다.

 

 

파이썬 코드로 구현

파이썬으로 다양하게 구현해볼 수 있다.

def gcd(m,n):
if m < n:
        m, n = n, m
if n == 0:
return m
if m % n == 0:
return n
else:
return gcd(n, m%n)

def gcd(m,n):
    while n != 0:
       t = m%n
       (m,n) = (n,t)
    return abs(m)

def gcd(m,n):
    while n! = 0:
        if m < n:
            m, n = n, m
        if n == 0:
            return m
        if m % n == 0:
            return n

def gcd(m,n):
    if n == 0:
        return m
    mod = m % n
    if mod != 0:
        m, n = n, mod
        return gcd(m, n)
    else:
        return n

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

 

 

관련 문제

1934번: 최소공배수

1934번: 최소공배수

 

 

참고 사이트

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

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