Friday, April 20, 2007

Python 파이썬] 최소공배수 구하기 함수; LCM

파이썬에서, 최소공배수(Least Common Multiple)를 구하는 방법입니다. 최소공배수를 구하려면 우선 최대공약수부터 구해야 합니다. 다음 예제와 같습니다:

최소 공배수 계산 예제
파일명: example.py

#!/usr/bin/python
# -*- coding: cp949 -*-

# 최대 공약수 구하기 함수: 최소 공배수 계산에 필요
# (Euclidean Algorithm; Euclid's Algorithm)
def gcd(a, b):
while (b != 0):
temp = a % b
a = b
b = temp
return abs(a)

# 최소 공배수 계산 함수
def lcm(a, b):
gcd_value = gcd(a, b)
if (gcd_value == 0): return 0 # 인수가 둘다 0일 때의 에러 처리
return abs( (a * b) / gcd_value )

# 테스트 시작
print lcm(4, 6) # 12
print lcm(21, 6) # 42
print lcm(-5, -4) # 20
print lcm(-9, 2) # 18
print lcm(0, 0) # 0

# 세 숫자의 최소공배수 구하기
result = lcm(45, lcm(120, 75))
print result # 1800

# 네 숫자의 최소공배수 구하기
result = lcm(112, lcm(113, lcm(114, 119)))
print result # 12263664