여기서 우리는 주어진 숫자의 최소 합을 구하는 방법을 볼 것입니다. 숫자가 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입니다. 우리는 숫자를 취하고 최소 요소 합을 찾으려고 노력할 것입니다. 최소 인수 합을 얻으려면 가능한 한 오랫동안 숫자를 인수분해해야 합니다. 즉, 소인수를 더하여 합 S를 구하면 합이 최소화된다고 말할 수 있습니다.
예시
#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