숫자의 홀수 약수의 합을 구하는 Python 프로그램

문제 개요

이 글에서는 다음과 같은 문제에 대한 해결 방법을 알아보겠습니다.

문제: 하나의 숫자 n이 주어졌을 때, n의 모든 홀수 약수의 합을 구하는 프로그램을 작성하는 것입니다.

예를 들어 n = 27이라면, 27의 약수 중 홀수는 1, 3, 9, 27이므로 정답은 1 + 3 + 9 + 27 = 40이 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 바로 짝수 약수를 먼저 모두 제거하는 것입니다.

n이 2로 나누어 떨어지는 동안 계속해서 2로 나누면, 남은 값은 더 이상 짝수 인수를 포함하지 않습니다. 따라서 이 시점 이후의 모든 약수는 자연스럽게 홀수뿐입니다.

그다음에는 남은 홀수 부분을 소인수분해하고, 각 소수 거듭제곱에 대해 등비수열의 합을 구한 뒤 모두 곱해주면 전체 홀수 약수의 합을 얻을 수 있습니다. 예를 들어 홀수 부분이 3³이라면 이 부분의 기여값은 1 + 3 + 9 + 27 = 40입니다.

구현 예제

import math

def sumofoddFactors(n):
    # 1단계: 짝수 약수 제거 (2로 나눌 수 있는 동안 계속 나눔)
    while n % 2 == 0:
        n = n // 2

    res = 1

    # 2단계: 남은 홀수 부분을 소인수분해하며 약수의 합 계산
    for i in range(3, int(math.sqrt(n)) + 1):
        curr_sum = 1   # 현재 소수에 대한 등비수열의 합
        curr_term = 1  # 현재 거듭제곱 항
        while n % i == 0:
            n = n // i
            curr_term *= i
            curr_sum += curr_term
        res *= curr_sum

    # 3단계: √n보다 큰 소수가 하나 남아 있는 경우 처리
    if n >= 2:
        res *= (1 + n)

    return res

# 메인 실행부
n = 27
print(sumofoddFactors(n))

실행 결과

40

코드 설명

• 짝수 제거: 첫 번째 while 루프에서 n을 2로 계속 나누어 짝수 인수를 완전히 제거합니다.
• 소인수별 합 산출: 각 소수 i에 대해 1 + i + i² + … + iᵏ(k는 지수)를 curr_sum에 누적한 후 res에 곱합니다.
• 큰 소수 처리: √n까지만 검사하므로, 루프 종료 후 1보다 큰 값이 남으면 그것은 반드시 소수이며 (1 + n)을 곱해 마무리합니다.
• 효율성: √n까지만 탐색하므로 전체 시간 복잡도는 O(√n)입니다.

검증

n = 27의 경우 27 = 3³이므로, 홀수 약수의 합은 1 + 3 + 9 + 27 = 40으로 프로그램 결과와 일치합니다. 참고로 n = 30일 때 홀수 약수는 1, 3, 5, 15이며 그 합은 24입니다.

마무리

이번 글에서는 숫자의 홀수 약수 합을 구하는 접근 방법을 살펴보았습니다. 핵심은 짝수 인수를 먼저 제거한 뒤, 소인수분해 기반의 등비수열 합 공식을 활용하는 것이며, 이를 통해 O(√n) 시간 안에 효율적으로 정답을 구할 수 있습니다.