양의 정수가 주어졌을 때, 그 숫자의 홀수 약수를 모두 찾아 합을 구하는 것이 이번 문제의 목표입니다. 예를 들어 20의 약수는 1, 2, 4, 5, 10, 20이고, 이 가운데 홀수인 약수는 1과 5뿐이므로 홀수 약수의 합은 6이 됩니다.
예제
입력: number = 20 출력: 홀수 약수의 합은 6 입력: number = 18 출력: 홀수 약수의 합은 13
18의 경우 약수는 1, 2, 3, 6, 9, 18이며, 그중 홀수 약수는 1, 3, 9입니다. 따라서 결과 = 1 + 3 + 9 = 13이 됩니다.
접근 방식
이 문제의 핵심은 소인수분해입니다. 어떤 수를 소인수분해했을 때 홀수 소수 p의 지수가 a라면, 해당 소수가 만들어내는 홀수 약수의 합은 1 + p + p² + ... + pᵃ 입니다. 모든 홀수 소수에 대해 이 값을 곱하면 전체 홀수 약수의 합을 구할 수 있습니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 홀수 약수의 합을 계산할 숫자를 입력받습니다.
- 숫자가 2로 나누어떨어지는 동안 계속 2로 나누어 짝수 인수를 제거합니다. 인수 2는 홀수 약수에 영향을 주지 않기 때문입니다.
- 3부터 숫자의 제곱근까지 반복문을 돌며 홀수 소인수를 찾습니다.
- num % i가 0이 되는 동안 num을 i로 계속 나누고, 임시 변수를 temp = temp * i로 갱신하면서 total에 누적합니다(total = total + temp).
- 각 소인수에 대해 구한 total 값을 res에 곱합니다(res = res * total).
- 반복이 끝난 후 남은 num이 2 이상이면 그 값 자체가 홀수 소수이므로 res *= (1 + num)을 적용합니다.
- 최종 res 변수의 값을 반환하고 결과를 출력합니다.
알고리즘
START
Step 1-> 홀수 약수의 합을 계산하는 함수 선언
int sum(int num)
int res = 1 선언
While(num % 2 == 0) 반복
num = num / 2
End
For(int i = 3; i <= sqrt(num); i++) 반복
int count = 0, total = 1 선언
int temp = 1 선언
While(num % i == 0) 반복
count++
num = num / i
temp *= i
total += temp
End
res = res * total
End
IF(num >= 2)
res *= (1 + num)
End
return res
Step 2-> main() 함수에서
int num = 20 선언
sum(num) 호출
STOP예제 코드
#include <bits/stdc++.h>
using namespace std;
// 홀수 약수의 합 계산
int sum(int num) {
int res = 1;
while (num % 2 == 0)
num = num / 2;
for (int i = 3; i <= sqrt(num); i++) {
int count = 0, total = 1;
int temp = 1;
while (num % i == 0) {
count++;
num = num / i;
temp *= i;
total += temp;
}
res = res * total;
}
if (num >= 2)
res *= (1 + num);
return res;
}
int main() {
int num = 20;
cout << "홀수 약수의 합 : ";
cout << sum(num);
return 0;
}출력
홀수 약수의 합 : 6
동작 원리 살펴보기
num = 20일 때의 실행 과정을 단계별로 살펴보겠습니다.
- 20은 2로 두 번 나누어떨어지므로 2로 나누면 5가 됩니다. (res = 1)
- i = 3부터 반복을 시작하지만 √5 ≈ 2.24보다 크므로 for 반복문은 실행되지 않습니다.
- 남은 num = 5가 2 이상이므로 res = 1 × (1 + 5) = 6이 됩니다.
- 따라서 최종 결과는 6입니다.
이 알고리즘은 시간 복잡도 O(√n)으로 동작하므로, 큰 수에 대해서도 효율적으로 홀수 약수의 합을 구할 수 있다는 장점이 있습니다.