파이썬으로 공약수·공배수 판별하고 최대공약수 구하기

공약수와 공배수 문제는 나머지 연산을 이해하면 간단해집니다. 다만 “주어진 수가 공배수인지 판별”하는 것과 “최소공배수를 계산”하는 것은 서로 다른 작업이므로 구분해야 합니다.

약수와 배수의 기준

number % divisor == 0이면 number는 divisor로 나누어떨어집니다. 따라서 divisor는 number의 약수이고 number는 divisor의 배수입니다.

number = 24
print(number % 6 == 0)  # True

공약수 찾기

def common_divisors(a, b):
    limit = min(abs(a), abs(b))
    return [n for n in range(1, limit + 1)
            if a % n == 0 and b % n == 0]

print(common_divisors(18, 24))  # [1, 2, 3, 6]

학습용으로는 이해하기 쉽지만 큰 수에서 모든 후보를 검사하면 비효율적입니다. 최대공약수만 필요하다면 표준 라이브러리를 사용합니다.

최대공약수와 최소공배수

from math import gcd

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

print(gcd(18, 24))  # 6
print(lcm(18, 24))  # 72

두 수의 곱은 최대공약수와 최소공배수의 곱과 연결됩니다. 음수 입력에도 양수 결과를 주도록 abs()를 사용했고, 0이 포함된 최소공배수는 이 함수에서 0으로 처리했습니다.

주어진 수가 공배수인지 판별

def is_common_multiple(number, a, b):
    if a == 0 or b == 0:
        return False
    return number % a == 0 and number % b == 0

print(is_common_multiple(60, 3, 5))  # True

0으로 나머지를 계산할 수 없으므로 기준값이 0인 상황을 먼저 처리해야 합니다.

세 수 이상의 최대공약수

from functools import reduce
from math import gcd

numbers = [24, 36, 60]
result = reduce(gcd, numbers)
print(result)  # 12

빈 목록에는 초기값이 없으므로 실제 함수에서는 입력 개수를 검사해야 합니다.

def my_gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

print(my_gcd(18, 24))  # 6

입력 조합으로 함수 검증하기

수학 함수는 정상 예제 하나만 확인하면 경계값에서 오류가 남기 쉽습니다. gcd(18, 24)뿐 아니라 두 수가 같은 경우, 한 수가 1인 경우, 0과 음수가 포함된 경우도 확인하십시오.

cases = [(18, 24), (7, 7), (1, 99), (0, 5), (-18, 24)]
for a, b in cases:
    print(a, b, gcd(a, b))

math.gcd()는 음수 입력에도 음수가 아닌 결과를 반환합니다. 직접 만든 함수가 같은 규칙을 따르는지 비교하면 구현 오류를 찾기 쉽습니다. 최소공배수 함수도 두 수의 순서를 바꿔 결과가 같은지 확인해 보세요.

정리

나누어떨어지는지 확인할 때는 %, 최대공약수 계산에는 math.gcd()를 사용합니다. 판별 문제와 계산 문제를 먼저 구분하고 0과 음수의 처리 규칙을 명시하십시오.