Tìm tổng nhỏ nhất của các ước số khi phân tích số n thành tích các ước.
Ví dụ n=12: 12=12*1 (tổng 13), 2*6 (8), 3*4 (7), 2*2*3 (7) -> min = 7.
Giải pháp
Phân tích thừa số nguyên tố, tổng các thừa số nguyên tố là tối thiểu.
Chương trình C++ ví dụ
#include <iostream>
using namespace std;
int main() {
int n = 12, sum = 0;
for (int i=2; i*i<=n; i++)
while (n%i==0) { sum+=i; n/=i; }
sum += n;
cout << sum;
return 0;
}Kết quả
7