유클리드 호제법

유클리드 알고리즘이란?

유클리드 알고리즘은 2개의 자연수 혹은 정식($\frac 1 2$나 $\sqrt 3$과 같이 분모나 근호 속에 문자를 포함하고 있지 않은 식)의 최대공약수를 구하는 알고리즘의 하나이다. '호제법'이란 말은 두 수가 서로 상대방의 수를 나눠 원하는 수를 얻는 알고리즘이다.

최대공약수 구하기

.

• 두개의 자연수 a,b에 대해서, a를 b로 나눈 나머지를 r이라고 한다. (a>b)
• a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
• b를 r로 나눈 나머지를 r'라고 한다.
• b와 r의 최대공약수는 r와 r'의 최대공약수와 같다.
• 위과정을 반복해서 나머지가 0이 될때 나누는 수가 최대공약수이다.

코드

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

위는 python 으로 작성한 유클리드 호제법을 활용한 최대공약수를 구하는 코드이다. a에는 작은 값이었던 b를 b에는 a를 b로 나눈 나머지를 할당해서 b가 0이 될때까지 반복해(나머지가 0이 될때 나누는 수 → a) a 를 반환한다.

최소공배수

서로 다른 수 a, b의 배수중에서 공통되는 배수 중에 가장 작은 값을 의미한다. 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.
ex)
14,6의 최소공배수
1) 14 $\times$ 6=84 (2 $\times$ 7 $\times$ 2 $\times$ 3 = $2^2 \times 3 \times 7$)
2) 84 $\div$ 2= 42 ($2 \times 3 \times 7$)

코드

이전의 gcd 최대공약수를 사용하여 쉽게 최소공배수도 구할 수 있다.

def lcm(a, b):
    return a * b / gcd(a, b)

---

Reference

https://velog.io/@jwisgenius/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98