এখানে আমরা দেখব কিভাবে একটি প্রদত্ত সংখ্যার গুণনীয়কের ন্যূনতম যোগফল পাওয়া যায়। ধরুন একটি সংখ্যা 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
