최대공약수(GCD/HCF)란 무엇인가?
두 개 이상의 정수에 대한 최대공약수(Highest Common Factor, HCF / Greatest Common Divisor, GCD)란, 해당 숫자들을 나머지 없이 나누어 떨어지게 하는 가장 큰 양의 정수를 의미합니다. 예를 들어, 8과 12의 최대공약수는 4입니다. 8의 약수는 1, 2, 4, 8이고 12의 약수는 1, 2, 3, 4, 6, 12이므로, 공통 약수 중 가장 큰 값인 4가 GCD가 됩니다.
방법 1: 반복문(for loop)을 이용한 기본 구현
가장 직관적인 방법은 두 수 중 작은 값까지 1부터 하나씩 확인하면서, 두 수를 모두 나누어 떨어지게 하는 가장 큰 수를 찾는 것입니다.
x = int(input("첫 번째 숫자를 입력하세요: "))
y = int(input("두 번째 숫자를 입력하세요: "))
# 두 수 중 작은 값을 기준으로 반복 범위 설정
if x > y:
smaller = y
else:
smaller = x
for i in range(1, smaller + 1):
if (x % i == 0) and (y % i == 0):
hcf = i
print(x, "와", y, "의 최대공약수는", hcf, "입니다.")실행 결과:
첫 번째 숫자를 입력하세요: 8
두 번째 숫자를 입력하세요: 12
8 과 12 의 최대공약수는 4 입니다.이 방식은 이해하기 쉽지만, 숫자가 커지면 1부터 일일이 검사해야 하므로 성능이 떨어질 수 있습니다.
방법 2: 유클리드 호제법(Euclidean Algorithm)
더 효율적인 방법으로 유클리드 호제법이 널리 사용됩니다. 두 수 a와 b(a > b)가 있을 때, a를 b로 나눈 나머지 r에 대해 GCD(a, b) = GCD(b, r)이 성립한다는 원리를 이용합니다. 나머지가 0이 될 때까지 반복하면 그 시점의 a가 곧 최대공약수입니다.
def gcd(a, b):
while b:
a, b = b, a % b
return a
num1 = int(input("첫 번째 숫자를 입력하세요: "))
num2 = int(input("두 번째 숫자를 입력하세요: "))
print("최대공약수:", gcd(num1, num2))유클리드 호제법은 반복 횟수가 매우 적기 때문에 큰 숫자에 대해서도 빠르게 동작합니다.
방법 3: math 모듈의 gcd() 함수 활용
파이썬 3.5 이상에서는 표준 라이브러리인 math 모듈에 내장된 math.gcd() 함수를 사용하면 한 줄로 해결할 수 있습니다.
import math
print(math.gcd(8, 12)) # 출력: 4
print(math.gcd(36, 60)) # 출력: 12실무에서는 별도의 알고리즘을 직접 구현하기보다 이처럼 표준 라이브러리를 활용하는 것이 코드의 안정성과 가독성 면에서 권장됩니다.
정리
- 반복문 방식: 원리 이해에 적합하지만 큰 수에는 비효율적
- 유클리드 호제법: 효율적이며 알고리즘 학습에 필수적인 접근법
- math.gcd(): 실무에서 가장 간편하고 신뢰할 수 있는 방법
상황에 맞는 방법을 선택하여 파이썬에서 손쉽게 최대공약수를 계산해 보세요.