유클리드 호제법을 이용한 최대공약수 (GCD) 구하기

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

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘입니다.

 

재귀호출을 통해서 구하는 방법과 반복문을 통해서 구하는 방법이 있습니다.

 

 

재귀호출을 이용하는 방법입니다.

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(x, y):   
        while(y): 
                x, y = y, x % y   
        return x 

 

라메의 정리에 의하면, 최대공약수를 구할 때, 소인수 분해를 이용하는 것 보다 유클리드 호제법을 이용하여 구하는 것이 훨씬 빠른 것으로 알려져있습니다.