다음은 파이썬에서 최대공약수와 최소공배수를 계산하고 구하는 방법에 대한 설명입니다.
- 두 정수의 최대공약수와 최소공배수
- 3개 이상의 정수의 최대공약수와 최소공배수
Python 버전에 따라 표준 라이브러리에서 제공하는 기능의 사양이 다르다는 점에 유의하시기 바랍니다. 표준 라이브러리에 없는 함수의 구현 예도 이 문서에 나와 있습니다.
- 파이썬 3.4 이하
- GCD:
fractions.gcd()(단 두 개의 인수)
- GCD:
- 파이썬 3.5 이상
- GCD:
math.gcd()(단 두 개의 인수)
- GCD:
- 파이썬 3.9 이상
- GCD:
math.gcd()(3개 이상의 인수 지원) - 최소 공통 분모:
math.lcm()(3개 이상의 인수 지원)
- GCD:
여기에서는 표준 Python 라이브러리를 사용하는 방법을 설명합니다. NumPy는 여러 배열의 각 요소에 대한 최대 공약수와 최소 공배수를 계산하는 데 쉽게 사용할 수 있습니다.
두 정수의 최대공약수와 최소공배수
GCD
Python 3.5부터 수학 모듈에 gcd() 함수가 있습니다. gcd()는 의 약어입니다.
- greatest common divisor
인수에 지정된 정수의 최대 공약수를 반환합니다.
import math
print(math.gcd(6, 4))
# 2
Python 3.4 및 이전 버전에서 gcd() 함수는 수학 모듈이 아니라 분수 모듈에 있습니다. fractions와 fractions.gcd()를 가져와야 합니다.
최소 공통 분모
최소 공배수를 반환하는 lcm() 함수는 Python 3.9의 수학 모듈에 추가되었습니다. lcm는 약어입니다.
- least common multiple
인수에 지정된 정수의 최소 공배수를 반환합니다.
print(math.lcm(6, 4))
# 12
Python 3.8 이전에는 lcm()가 제공되지 않았지만 gcd()를 사용하여 쉽게 계산할 수 있습니다.
lcm(a, b) = a * b / gcd(a, b)
구현 예.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/그 결과 십진 부동 소수점이 생성되기 때문에 두 개의 백슬래시를 사용하여 소수점을 자르고 정수 나누기 결과를 반환합니다. 인수가 정수인지 여부를 판별하는 처리는 수행되지 않습니다.
3개 이상의 정수의 최대공약수와 최소공배수
파이썬 3.9 이상
Python 3.9부터 다음 함수는 모두 3개 이상의 인수를 지원합니다.
math.gcd()math.lcm()
print(math.gcd(27, 18, 9))
# 9
print(math.gcd(27, 18, 9, 3))
# 3
print(math.lcm(27, 9, 3))
# 27
print(math.lcm(27, 18, 9, 3))
# 54
*목록 요소의 최대 공약수 또는 최소 공배수를 계산하려면 인수를 지정하십시오.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 또는 이전 버전
Python 3.8 이전에는 gcd() 함수가 두 개의 인수만 지원했습니다.
세 개 이상의 정수의 최대 공약수 또는 최소 공배수를 찾기 위해 특별히 복잡한 알고리즘이 필요하지 않습니다. 고차 함수 reduce()를 사용하여 여러 값 각각에 대한 최대 공약수 또는 최소 공배수를 차례로 계산하면 됩니다.
GCD
from functools import reduce
def my_gcd(*numbers):
return reduce(math.gcd, numbers)
print(my_gcd(27, 18, 9))
# 9
print(my_gcd(27, 18, 9, 3))
# 3
l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3
다시 말하지만, Python 3.4 이전에는 gcd() 함수가 수학 모듈이 아니라 fraction 모듈에 있었습니다.
최소 공통 분모
def my_lcm_base(x, y):
return (x * y) // math.gcd(x, y)
def my_lcm(*numbers):
return reduce(my_lcm_base, numbers, 1)
print(my_lcm(27, 9, 3))
# 27
print(my_lcm(27, 18, 9, 3))
# 54
l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54
