समस्या विवरण
यह प्रोग्राम किसी संख्या के सभी सम गुणनखंड ढूंढता है और इन सम गुणनखंडों का योग गणना करके आउटपुट के रूप में प्रदर्शित करता है।
उदाहरण
Input: 30 Even divisors: 2 + 6 + 10 + 30 = 48 Output: 48
दृष्टिकोण
इसके लिए, हम सभी गुणनखंड ढूंढेंगे। उनमें से सम गुणनखंड ढूंढेंगे और उनका योग निकालेंगे।
अन्यथा, हम अभाज्य गुणनखंडों का उपयोग करके गुणनखंडों के योग का सूत्र उपयोग करेंगे:
गुणनखंडों का योग = (1 + d₁¹ + d₁² ... d₁^a₁) × (1 + d₂¹ + d₂² ... d₂^a₂) × ... × (1 + dₖ¹ + dₖ² ... dₖ^aₖ) जहां dᵢ = अभाज्य गुणनखंड; aᵢ = dᵢ की घात
हमें केवल सम गुणनखंड चाहिए, इसलिए यदि संख्या विषम है तो कोई सम गुणनखंड मौजूद नहीं होगा। उस स्थिति में हम 0 आउटपुट करेंगे।
उदाहरण
#include <iostream>
#include <cmath>
using namespace std;
long long sumEvenFactors(int n) {
int original = n;
// यदि संख्या विषम है, तो कोई सम गुणनखंड नहीं
if (n % 2 != 0) {
return 0;
}
long long evenSum = 1;
// 2 का गुणनखंड अलग से हैंडल करें
int count = 0;
long long currSum = 1, currTerm = 1;
while (n % 2 == 0) {
count++;
n = n / 2;
if (count == 1) {
currSum = 0; // 2^0 = 1 को बाहर रखें (सम गुणनखंड के लिए)
}
currTerm *= 2;
currSum += currTerm;
}
evenSum *= currSum;
// विषम अभाज्य गुणनखंडों के लिए
for (int i = 3; i <= sqrt(n); i += 2) {
count = 0;
currSum = 1;
currTerm = 1;
while (n % i == 0) {
count++;
n = n / i;
currTerm *= i;
currSum += currTerm;
}
evenSum *= currSum;
}
// यदि n अभी भी एक अभाज्य संख्या है (> 2)
if (n >= 2) {
evenSum *= (1 + n);
}
return evenSum;
}
int main() {
int n = 12;
cout << "The sum of all even factors of " << n << " is " << sumEvenFactors(n);
return 0;
}आउटपुट
The sum of all even factors of 12 is 24
सत्यापन
12 के गुणनखंड: 1, 2, 3, 4, 6, 12
सम गुणनखंड: 2, 4, 6, 12
योग: 2 + 4 + 6 + 12 = 24 ✓
सरल दृष्टिकोण (O(√n))
long long sumEvenFactorsSimple(int n) {
if (n % 2 != 0) return 0;
long long sum = 0;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
if (i % 2 == 0) sum += i;
int pair = n / i;
if (pair != i && pair % 2 == 0) sum += pair;
}
}
// n स्वयं भी एक गुणनखंड है
if (n % 2 == 0) sum += n;
return sum;
}समय जटिलता
- अभाज्य गुणनखंड विधि: O(√n)
- सरल विधि: O(√n)
