Python에서 배열 요소의 LCM이 소수로 나누어 떨어지는지 확인하는 방법

문제 상황

배열 nums와 값 k가 주어졌을 때, 배열에 들어 있는 모든 숫자의 최소공배수(LCM)가 k로 나누어 떨어지는지 판별해야 합니다.

예를 들어 nums = [12, 15, 10, 75], k = 10이라고 해보겠습니다. 각 요소를 소인수분해하면 12 = 2² × 3, 15 = 3 × 5, 10 = 2 × 5, 75 = 3 × 5²이므로 전체 LCM은 2² × 3 × 5² = 300입니다. 300은 10으로 나누어 떨어지기 때문에 결과는 True가 됩니다.

핵심 아이디어: LCM을 직접 구하지 않아도 된다

k가 소수(prime)인 경우에는 유용한 성질을 활용할 수 있습니다. 소수 p에 대해서는 "여러 수의 LCM이 p로 나누어 떨어진다"와 "그 수들 중 적어도 하나가 p로 나누어 떨어진다"가 서로 동치입니다. 즉, k가 소수일 때 다음이 성립합니다.

k | LCM(nums) ⇔ nums[i] % k == 0을 만족하는 i가 하나 이상 존재

따라서 배열 전체의 LCM을 계산할 필요 없이, 배열을 한 번만 순회하면서 k로 나누어 떨어지는 요소가 있는지만 확인하면 됩니다.

알고리즘 단계

인덱스 0부터 len(nums) - 1까지 배열을 순회합니다.
현재 요소 nums[i]가 k로 나누어 떨어지면 즉시 True를 반환합니다.
순회가 끝날 때까지 조건을 만족하는 요소가 없었다면 False를 반환합니다.

구현 코드

def solve(nums, k):
    for i in range(len(nums)):
        if nums[i] % k == 0:
            return True
    return False

nums = [12, 15, 10, 75]
k = 10
print(solve(nums, k))

입력

[12, 15, 10, 75], 10

출력

True

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
공간 복잡도: O(1) — 추가 메모리가 거의 필요하지 않습니다.

주의: k가 소수가 아닐 때

위 방식은 k가 소수일 때만 정확하게 동작합니다. k가 합성수라면 단순 비교로는 부족할 수 있습니다. 예를 들어 nums = [2, 3], k = 6인 경우 LCM은 6으로 나누어 떨어지지만, 개별 요소 2와 3 중 어느 것도 6으로 나누어 떨어지지 않습니다.

이럴 때는 LCM을 직접 계산해 확인하는 것이 안전합니다. Python 3.9 이상에서는 math.lcm()을 바로 사용할 수 있습니다.

from math import lcm

def solve(nums, k):
    return lcm(*nums) % k == 0

그 이전 버전에서는 math.gcd()를 이용해 두 수씩 LCM을 구해 누적하면 됩니다.

from math import gcd
from functools import reduce

def lcm_pair(a, b):
    return a * b // gcd(a, b)

def solve(nums, k):
    return reduce(lcm_pair, nums) % k == 0