개요
이 글에서는 주어진 숫자의 인수(약수) 합 중 최솟값을 구하는 방법을 알아봅니다. 예를 들어 숫자가 12라면, 다음과 같이 여러 가지 방식으로 인수분해할 수 있습니다.
- 12 = 12 × 1 (12 + 1 = 13)
- 12 = 2 × 6 (2 + 6 = 8)
- 12 = 3 × 4 (3 + 4 = 7)
- 12 = 2 × 2 × 3 (2 + 2 + 3 = 7)
이 경우 최소 합은 7입니다. 숫자를 입력받아 인수의 최소 합을 구하는 프로그램을 만들어 보겠습니다. 인수 합을 최소화하려면 숫자를 가능한 한 잘게 쪼개야 합니다. 다시 말해, 소인수분해를 통해 얻은 소인수들을 모두 더한 값이 곧 최소 합이 됩니다.
알고리즘 설명
primeFactorSum 함수는 2부터 시작해 √n 이하의 모든 수에 대해 n을 나누어 떨어지는지 검사합니다. 나누어 떨어질 때마다 해당 약수를 합에 더하고, n을 그 값으로 나눕니다. 반복문이 종료된 후 남아 있는 n은 1보다 큰 소수이므로, 마지막으로 합에 더해주면 됩니다. 이 알고리즘의 시간 복잡도는 O(√n)입니다.
예제 코드
#include<iostream>
using namespace std;
int primeFactorSum(int n) {
int s = 0;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
s += i;
n /= i;
}
}
s += n;
return s;
}
int main() {
int n = 12;
cout << "Minimum sum of factors: " << primeFactorSum(n);
}실행 결과
Minimum sum of factors: 7
정리
숫자의 인수 합을 최소화하려면 단순히 두 개의 인수 조합을 비교하는 것이 아니라, 소인수분해를 끝까지 수행한 뒤 모든 소인수를 더하는 것이 핵심입니다. 위 코드처럼 2부터 √n까지 나눗셈을 반복하면 효율적으로 소인수의 합을 계산할 수 있습니다.