이 글에서는 주어진 숫자 n에 대해 짝수 약수(even factors)의 합을 구하는 방법을 Python 코드와 함께 알아보겠습니다.
문제 정의
숫자 n이 입력으로 주어졌을 때, 그 수의 모든 짝수 약수를 찾아 합계를 구하는 것이 목표입니다.
예를 들어 n = 20이라면, 20의 약수는 1, 2, 4, 5, 10, 20이고, 이 중 짝수인 약수는 2, 4, 10, 20이므로 합은 2 + 4 + 10 + 20 = 36이 됩니다.
접근 방식
핵심 아이디어는 다음과 같습니다.
- 먼저 홀수인 약수들을 제외해야 합니다.
- 입력된 숫자가 홀수라면 짝수 약수가 존재할 수 없으므로 즉시 0을 반환합니다.
- 숫자가 짝수라면 소인수분해를 활용해 약수의 합 공식을 적용하되, 2의 0제곱(즉, 1) 항목을 제거하여 짝수 약수만 계산합니다.
약수의 합 공식에서 각 소인수 p가 k번 거듭제곱으로 포함될 때 (1 + p + p² + ... + pᵏ) 형태의 항이 곱해지는데, 여기서 2에 해당하는 항에서 1(=2⁰)을 빼면 자연스럽게 짝수 약수만 남게 됩니다.
구현 코드
import math
# n의 모든 짝수 약수의 합을 반환합니다.
def sumofFactors(n) :
# n이 홀수인 경우
if (n % 2 != 0) :
return 0
# 소인수분해 기반 약수의 합 계산
res = 1
for i in range(2, (int)(math.sqrt(n)) + 1) :
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 = 20
print(sumofFactors(n))실행 결과
36
코드 동작 원리
위 코드의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- 홀수 판별: n을 2로 나눈 나머지가 0이 아니면 짝수 약수가 없으므로 0을 반환합니다.
- 소인수분해: 2부터 √n까지의 수로 n을 반복해서 나누며 각 소인수의 지수(count)를 셉니다.
- 짝수 약수 처리: 소인수가 2일 때 첫 번째 항(curr_term = 1)을 합계에서 제외하여 홀수 약수를 걸러냅니다.
- 남은 소수 처리: 루프 종료 후 n이 2 이상으로 남아 있다면 그것은 √n보다 큰 소인수이므로 (1 + n)을 결과에 곱합니다.
n = 20의 경우, 20 = 2² × 5이므로 짝수 약수의 합은 (2 + 4) × (1 + 5) = 6 × 6 = 36으로 계산되어 출력 결과와 일치합니다.
시간 복잡도
이 알고리즘은 √n까지만 반복하므로 시간 복잡도는 O(√n)입니다. 단순히 1부터 n까지 모든 수를 순회하며 약수를 확인하는 O(n) 방식보다 효율적입니다.
결론
이 글에서는 소인수분해와 약수의 합 공식을 활용하여 숫자의 짝수 약수의 합을 효율적으로 구하는 Python 프로그램을 살펴보았습니다. 입력값이 홀수인 경우를 먼저 처리하고, 2⁰ 항을 제거하는 아이디어만으로 불필요한 연산 없이 정답을 빠르게 얻을 수 있습니다.