유클리드 호제법 - 최대공약수(GCD) 구하기
1. 유클리드 호제법이란?
유클리드 호제법은 두 개의 자연수의 최대공약수를 구하는 방법 중 하나로, 낮은 수를 고정하고 높은 수를 낮은 수로 나눈 나머지를 구한 후, 나머지가 0이 될 때까지 반복하여 최대공약수를 구하는 알고리즘이다.
2. 유클리드 호제법의 원리
두 수 A, B의 최대공약수를 구하기 위해 A를 B로 나눈 나머지를 R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 이러한 원리를 반복하여 나머지가 0이 될 때까지 나누면, 마지막으로 나눈 수가 두 수의 최대공약수가 된다.
3. 유클리드 호제법의 구현
유클리드 호제법을 구현하는 방법은 다음과 같다.
def gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a위의 코드는 두 수 a와 b의 최대공약수를 구하는 함수로, 반복문을 통해 b가 0이 될 때까지 나누고 남은 나머지를 계속해서 업데이트하는 방식으로 최대공약수를 구한다.
4. 예시
아래는 두 수 120과 84의 최대공약수를 구하는 과정이다.
- 120을 84로 나누면 나머지는 36이다.
- 84를 36으로 나누면 나머지는 12이다.
- 36을 12로 나누면 나머지는 0이다.
나머지가 0이 되었으므로, 최종적으로 남은 수인 12가 두 수 120과 84의 최대공약수이다.
마무리
유클리드 호제법은 두 수의 최대공약수를 구하는 효율적인 방법 중 하나로, 낮은 수를 고정하고 높은 수를 낮은 수로 나눈 나머지를 구하는 것이 핵심이다. 이러한 원리를 반복하여 나머지가 0이 될 때까지 나누고, 마지막으로 나눈 수를 두 수의 최대공약수로 반환한다.
댓글