[Python] 최대공약수 (gcd) / 최소공배수 (lcm)

1. gcd() 함수

gcd() 함수는 두 숫자의 최대 공약수를 반환합니다. 최대 공약수는 두 수를 동시에 나눌 수 있는 가장 큰 양의 정수입니다.

문법

import math
math.gcd(a, b)

• a, b: 두 개의 정수 값.
• 반환 값: 두 수의 최대 공약수.

예시

import math
print(math.gcd(48, 18))  # 6

• 48과 18의 최대 공약수는 6입니다.

2. lcm() 함수

파이썬 표준 라이브러리에는 lcm() 함수가 없지만, 최대 공약수를 활용해 최소 공배수를 구할 수 있습니다. 최소 공배수는 두 수의 공통 배수 중 가장 작은 양의 정수입니다.

최소 공배수 계산 공식

두 수 a, b의 최소 공배수는 다음과 같이 구할 수 있습니다:

직접 구현 예시

import math

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

print(lcm(48, 18))  # 144

• 48과 18의 최소 공배수는 144입니다.

3. gcd와 lcm 활용 예시

# 여러 수의 최대 공약수와 최소 공배수 구하기
numbers = [24, 36, 48]

# 최대 공약수
gcd_result = math.gcd(math.gcd(numbers[0], numbers[1]), numbers[2])
print(gcd_result)  # 12

# 최소 공배수
lcm_result = lcm(lcm(numbers[0], numbers[1]), numbers[2])
print(lcm_result)  # 144

---

여러 수의 최대 공약수(GCD) 구하기

여러 수의 최대 공약수는 다음과 같이 구할 수 있습니다:

즉, 두 수씩 최대 공약수를 구하고, 그 결과를 다음 수와 비교하여 반복적으로 GCD를 계산합니다.

import math

def gcd_multiple(numbers):
    gcd_result = numbers[0]
    for num in numbers[1:]:
        gcd_result = math.gcd(gcd_result, num)
    return gcd_result

numbers = [24, 36, 48]
print(gcd_multiple(numbers))  # 12

여러 수의 최소 공배수(LCM) 구하기

여러 수의 최소 공배수는 다음과 같이 구할 수 있습니다:

import math

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

def lcm_multiple(numbers):
    lcm_result = numbers[0]
    for num in numbers[1:]:
        lcm_result = lcm(lcm_result, num)
    return lcm_result

numbers = [24, 36, 48]
print(lcm_multiple(numbers))  # 144

정리

• 최대 공약수(gcd)는 두 수의 공통된 약수 중 가장 큰 값을 의미하며, 파이썬의 math.gcd() 함수로 쉽게 구할 수 있습니다.
• 최소 공배수(lcm)는 두 수의 공통된 배수 중 가장 작은 값을 의미하며, 최대 공약수를 사용해 계산할 수 있습니다.