Tìm tổng các thừa số tối thiểu của số bằng C ++.

Ở đây chúng ta sẽ xem làm thế nào để có được tổng các thừa số tối thiểu của một số nhất định. Giả sử một số là 12. Chúng ta có thể phân tích điều này theo những 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 tôi sẽ lấy một số và cố gắng tìm tổng thừa số nhỏ nhất. Để có tổng thừa 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 cố gắng tìm tổng S bằng cách thêm các thừa số nguyên tố, thì tổng đó sẽ bị 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);
}

Đầu ra

Minimum sum of factors: 7