Python으로 숫자의 짝수 약수의 합 구하는 방법

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

문제 정의 − 하나의 숫자 n이 주어졌을 때, 해당 숫자의 모든 짝수 약수(even factor)의 합을 구하여 출력해야 합니다.

접근 방법

먼저 주어진 수가 홀수인지 확인합니다. 홀수라면 짝수 약수가 존재할 수 없으므로 즉시 0을 반환합니다.

숫자가 짝수라면 본격적인 계산을 진행합니다. 약수의 합 공식에서 2⁰(즉 1)에 해당하는 항을 제외한 나머지 항들을 곱하면 곧 짝수 약수의 합이 됩니다.

즉, 짝수 약수 목록에서 홀수 성분을 걷어내려면 2⁰ = 1인 항을 무시하면 됩니다. 이 과정을 거치고 나면 짝수 약수만 남게 됩니다. 참고로 2는 존재하는 유일한 짝수 소수입니다.

예를 들어 n = 22인 경우, 22의 약수는 1, 2, 11, 22이며 이중 짝수는 2와 22입니다. 따라서 짝수 약수의 합은 2 + 22 = 24가 됩니다.

구현 예시

# math 모듈 임포트
import math

# n의 모든 짝수 약수의 합을 반환하는 함수
def sumofevenFactors(n) :
    # n이 홀수인 경우
    if (n % 2 != 0) :
        return 0

    # 순회 시작
    res = 1
    for i in range(2, (int)(math.sqrt(n)) + 1) :
        # i가 n을 나누는 경우
        count = 0
        curr_sum = 1
        curr_term = 1
        while (n % i == 0) :
            count = count + 1
            n = n // i
            # 여기서 2^0(즉 1)을 제외하고
            # 나머지 약수만 더한다
            if (i == 2 and count == 1) :
                curr_sum = 0
            curr_term = curr_term * i
            curr_sum = curr_sum + curr_term
        res = res * curr_sum

    # n이 소수로 남아 있는 경우
    if (n >= 2) :
        res = res * (1 + n)
    return res

# 메인 실행부
n = 22
print(sumofevenFactors(n))

출력 결과

24

위 코드에서 사용된 모든 변수와 함수는 전역 범위(global scope)에서 선언되어 프로그램 어디에서나 접근할 수 있습니다.

동작 원리 요약

이 알고리즘은 소인수분해를 활용합니다. √n까지의 수로 나누어 떨어질 때마다 몫을 갱신하면서 각 소인수의 지수를 세고, 2의 경우 첫 번째 항(2⁰ = 1)을 건너뛰어 짝수 약수만 합산 대상에 포함시킵니다. 마지막으로 2 이상의 값이 남아 있다면 그것은 소수이므로 (1 + n)을 곱해 최종 결과를 완성합니다. 시간 복잡도는 O(√n)으로 효율적입니다.

결론

이 글에서는 Python을 이용해 주어진 숫자의 짝수 약수의 합을 구하는 방법을 살펴보았습니다. 홀수 입력에 대한 예외 처리와 소인수분해 기반의 효율적인 순회 방식을 응용하면 다양한 수학적 문제 해결에도 활용할 수 있습니다.