최대공약수(GCD, Greatest Common Divisor)는 두 수를 각각 나누었을 때 나머지가 0이 되도록 하는 가장 큰 수를 찾는 수학적 개념입니다. 분수 약분, 암호학, 알고리즘 설계 등 다양한 수학적·프로그래밍 분야에서 널리 활용됩니다.
파이썬에서는 math 모듈에 내장된 gcd() 함수를 사용하면 별도의 알고리즘 구현 없이 최대공약수를 손쉽게 계산할 수 있습니다. 이 함수는 파이썬 3.5 버전부터 공식적으로 제공됩니다.
gcd() 함수란?
gcd() 함수는 두 개의 정수를 매개변수로 받아, 두 수의 최대공약수를 정수 형태로 반환합니다.
구문
Syntax: gcd(x, y)
여기서 x와 y는 정수입니다.
gcd() 함수 예제
아래 예제에서는 여러 쌍의 정수에 대해 gcd() 함수를 호출하고 그 결과를 출력합니다. 양수뿐만 아니라 0이나 음수가 포함된 경우에도 어떻게 동작하는지 확인할 수 있습니다.
import math
print("GCD of 75 and 30 is ", math.gcd(75, 30))
print("GCD of 0 and 12 is ", math.gcd(0, 12))
print("GCD of 0 and 0 is ", math.gcd(0, 0))
print("GCD of -24 and -18 is ", math.gcd(-24, -18))
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
GCD of 75 and 30 is 15
GCD of 0 and 12 is 12
GCD of 0 and 0 is 0
GCD of -24 and -18 is 6
결과 해석 및 참고 사항
- 75와 30의 GCD는 15: 두 수를 모두 나눌 수 있는 가장 큰 수입니다.
- 0과 12의 GCD는 12: 한쪽이 0일 경우, 나머지 수의 절댓값이 최대공약수가 됩니다.
- 0과 0의 GCD는 0: 수학적 관례상 gcd(0, 0)은 0으로 정의됩니다.
- -24와 -18의 GCD는 6: 음수가 입력되더라도 절댓값을 기준으로 계산되므로 항상 0 또는 양수가 반환됩니다.
내부적으로 math.gcd()는 유클리드 호제법(Euclidean Algorithm)을 기반으로 동작하므로, 매우 큰 수에 대해서도 빠르게 결과를 반환합니다. 두 수의 최대공약수가 필요할 때는 직접 반복문을 작성하기보다 이 내장 함수를 활용하는 것이 코드의 가독성과 성능 면에서 모두 유리합니다.