[Algorithm] 유클리드 호제법

유클리드 호제법

가장 빠르고 쉽게 최대공약수를 구할 수 있는 효율적인 알고리즘이다.

알고리즘

두 수를 a,b (a>b) 라고 할 때, r 을 a를 b로 나눈 나머지라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질을 따라 다시 b를 r로 나눈 r'를 구하고 이를 나머지가 0 이 될때까지 반복하는 알고리즘이다.

예시

a = 1071, b = 1029

1071%1029 = 42 - 0이 아니므로 연산을 계속한다

 -> 1029 % 42 = 21 - 0이 아니므로 연산을 계속한다

-> 42 % 21 = 0 - 나머지가 0이 되었으므로 연산을 종료한다

 ... 따라서 최대공약수는 21

최대공약수를 이용해 최소공배수도 구할 수 있다.

최소공배수 = a*b / 최대공약수

파이썬 코드로 구현한 최대공약수, 최소공배수 코드

def solution(n, m):     if m>n:         n ,m = m, n     r1,r2 = n, m%n     while not r2==0:         r1,r2 = r2, r1%r2     return [r1, n*m//r1]

cs