유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 호제법 - 최대공약수(GCD) 구하기

개요

유클리드 호제법은 두 개의 자연수의 최대공약수(Greatest Common Divisor, 이하 GCD)를 구하는 알고리즘이다. 이 알고리즘은 대표적인 재귀적인 방법으로, 두 수의 나누기 연산의 나머지를 이용하여 GCD를 구하는 방식이다.

알고리즘

두 수 A와 B의 GCD는 A를 B로 나눈 나머지 R과 B의 GCD와 같다는 원리를 기반으로 한다. 즉, GCD(A, B) = GCD(B, R)임을 이용하는 것이다. 이 과정을 두 수 중 하나가 0이 될 때까지 반복하면, 최종적으로 남은 0이 아닌 수가 두 수의 GCD가 된다.

예시

두 수 48과 60의 GCD를 구해보자.

• GCD(48, 60) = GCD(60, 48) = GCD(48, 12) = GCD(12, 0)
• 따라서, GCD(48, 60) = 12가 된다.

구현

유클리드 호제법은 다양한 프로그래밍 언어로 구현할 수 있지만, 기본적인 아이디어는 동일하다. 아래는 Python으로 구현한 예시 코드이다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 예시 실행
a = 48
b = 60
result = gcd(a, b)
print(f"GCD({a}, {b}) = {result}") # GCD(48, 60) = 12 출력

활용

유클리드 호제법은 정수론에서 주로 사용되며, 주어진 두 수 A와 B의 GCD를 구하는 문제의 해결에 이용된다. 또한, 두 수의 GCD를 이용하여 최소공배수(LCM)를 구하는 등 다양한 수학적 문제에 응용될 수 있다.

마무리

유클리드 호제법은 두 수의 GCD를 효율적으로 구하는 알고리즘이다. 재귀적인 방법으로 구현되어 있으며, 나누기 연산의 나머지를 활용하여 계산을 수행한다. 다양한 목적으로 활용 가능한 이 알고리즘은 수학 및 프로그래밍에서 유용하게 사용될 수 있다.