Ở đây chúng ta sẽ thấy cách lấy tổng tối thiểu của các ước số của một số cho trước. Giả sử một số là 12. Chúng ta có thể phân tích nó theo nhiều cách khác nhau:
- 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)
Tổng tối thiểu là 7. Chúng ta sẽ lấy một số, và thử tìm tổng ước số tối thiểu. Để có tổng ước số tối thiểu, chúng ta phải phân tích số đó càng lâu càng tốt. Nói cách khác, chúng ta có thể nói nếu chúng ta thử tìm tổng S bằng cách cộng các thừa số nguyên tố, thì tổng sẽ được tối thiểu hóa.
Ví dụ
#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); }
Kết quả
Minimum sum of factors: 7