এই সমস্যায়, আমাদের একটি প্রাকৃতিক সংখ্যা N দেওয়া আছে। আমাদের কাজ হল প্রাকৃতিক সংখ্যার সব ভাজকের ভাজকের যোগফল খুঁজে বের করা।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : N = 12 আউটপুট : 55
ব্যাখ্যা:
12-এর ভাজকগুলি: 1, 2, 3, 4, 6, 12 ভাজকগুলোর যোগফল = (1) + (1+2) + (1+3) + (1+2+4) + (1+2+3+6) + (1+2+3+4+6+12) = 1 + 3 + 4 + 7 + 12 + 28 = 55
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল N-এর গুণনিখণ্ডন (prime factorisation) ব্যবহার করা। প্রাইম ফ্যাক্টরাইজেশন দিয়ে আমরা সব ভাজকের ভাজকের যোগফল বের করতে পারি। এখানে আমরা প্রতিটি উপাদানের প্রাইম ফ্যাক্টরাইজেশন বের করব।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include<bits/stdc++.h>
using namespace std;
int findSumOfDivisorsOfDivisors(int n) {
map<int, int> factorCount;
for (int j = 2; j <= sqrt(n); j++) {
int count = 0;
while (n % j == 0) {
n /= j;
count++;
}
if (count)
factorCount[j] = count;
}
if (n != 1)
factorCount[n] = 1;
int sumOfDiv = 1;
for (auto it : factorCount) {
int power = 1;
int sum = 0;
for (int i = it.second + 1; i >= 1; i--) {
sum += (i * power);
power *= it.first;
}
sumOfDiv *= sum;
}
return sumOfDiv;
}
int main() {
int n = 12;
cout << "The sum of divisors of all divisors is " << findSumOfDivisorsOfDivisors(n);
return 0;
}
আউটপুট
The sum of divisors of all divisors is 55
