ที่นี่เราจะดูวิธีหาผลรวมตัวประกอบ (Sum of Factors) น้อยที่สุดของจำนวนที่กำหนด สมมติจำนวนคือ 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 โดยการบวกตัวประกอบเฉพาะ (Prime Factors) ผลรวมจะถูกทำให้เหลือน้อยที่สุด
ตัวอย่างโค้ด
#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
