Python으로 숫자의 약수 개수가 홀수인지 짝수인지 확인하는 방법

어떤 숫자 n이 주어졌을 때, 그 숫자의 약수(divisor) 개수가 홀수인지 짝수인지 판별하는 문제입니다.

예를 들어 입력이 n = 75라면, 약수는 [1, 3, 5, 15, 25, 75]로 총 6개이므로 출력 결과는 'Even'(짝수)이 됩니다.

접근 방법

이 문제는 아주 간단하면서도 효율적인 방법으로 해결할 수 있습니다. 핵심은 다음과 같은 수학적 성질입니다.

오직 완전제곱수(perfect square)만이 홀수 개의 약수를 가집니다.

일반적으로 약수는 서로 쌍을 이룹니다. 예를 들어 12의 경우 (1, 12), (2, 6), (3, 4)처럼 곱했을 때 n이 되는 두 수가 한 쌍을 이루므로 약수의 개수는 항상 짝수입니다. 하지만 완전제곱수의 경우 제곱근이 자기 자신과 한 쌍을 이루게 됩니다(예: 36 = 6 × 6). 이 때문에 완전제곱수만 약수의 개수가 홀수가 됩니다.

따라서 숫자가 완전제곱수인지만 확인하면, 그 결과에 따라 'Odd' 또는 'Even'을 바로 반환할 수 있습니다.

풀이 절차

• n < 1이면 함수를 종료합니다.
• sqrt := n의 제곱근을 구합니다.
• sqrt × sqrt가 n과 같으면 'Odd'를 반환합니다.
• 그렇지 않으면 'Even'을 반환합니다.

구현 예제

def solve(n):
    if n < 1:
        return
    sqrt = n**0.5
    if sqrt*sqrt == n:
        return 'Odd'
    else:
        return 'Even'

n = 75
print(solve(n))

입력

75

출력

Even

참고: 더 안전한 제곱근 검사

위 코드는 부동소수점 연산을 사용하기 때문에 매우 큰 숫자에서는 오차가 발생할 수 있습니다. Python 3.8 이상에서는 정수 연산만 사용하는 math.isqrt()를 활용하면 더 정확하게 판별할 수 있습니다.

import math

def solve(n):
    if n < 1:
        return
    sqrt = math.isqrt(n)
    if sqrt * sqrt == n:
        return 'Odd'
    else:
        return 'Even'

이 방법은 시간 복잡도가 O(1)에 가깝기 때문에, 모든 약수를 하나씩 세는 O(n) 또는 O(√n) 방식보다 훨씬 효율적입니다.