ที่นี่เราจะมาดูวิธีหาผลรวมตัวประกอบขั้นต่ำของจำนวนที่กำหนด สมมติว่าตัวเลขคือ 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
