समस्या विवरण
इस खंड में हम देखेंगे कि हम किसी संख्या के सभी सम अभाज्य गुणनखंडों का योग कुशल तरीके से कैसे प्राप्त कर सकते हैं। मान लीजिए एक संख्या n = 480 है, हमें इसके सभी गुणनखंड प्राप्त करने हैं। 480 के अभाज्य गुणनखंड 2, 2, 2, 2, 2, 3, 5 हैं। सभी सम गुणनखंडों का योग 2+2+2+2+2 = 10 है।
नियम
- जब संख्या 2 से विभाज्य हो, तो उन्हें योग में जोड़ें, और संख्या को बार-बार 2 से विभाजित करें
- अब संख्या विषम होनी चाहिए। इसलिए हमें कोई गुणनखंड नहीं मिलेगा जो सम हो। फिर बस उन गुणनखंडों को अनदेखा करें
एल्गोरिदम
printPrimeFactors(n):
begin
sum := 0
while n is divisible by 2:
sum := sum + 2
n := n / 2
done
end
उदाहरण
#include <iostream>
using namespace std;
int sumEvenFactors(int n) {
int sum = 0;
// केवल 2 से विभाज्य होने तक 2 जोड़ते रहें
while(n % 2 == 0) {
sum += 2;
n = n / 2; // 2 से विभाजित करके n को कम करें
}
return sum;
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout << "Sum of all even prime factors: " << sumEvenFactors(n);
return 0;
}आउटपुट
Enter a number: 480 Sum of all even prime factors: 10
व्याख्या
480 = 2 × 2 × 2 × 2 × 2 × 3 × 5 सम अभाज्य गुणनखंड: 2, 2, 2, 2, 2 (पांच बार) योग = 2 + 2 + 2 + 2 + 2 = 10
नोट: सम गुणनखंड बनाम सम अभाज्य गुणनखंड
मूल लेख में "सम गुणनखंड" (even factors) और "सम अभाज्य गुणनखंड" (even prime factors) में भ्रम है:
- सम अभाज्य गुणनखंड: केवल अभाज्य संख्या 2 (एकमात्र सम अभाज्य) - उपरोक्त कोड यही करता है
- सम गुणनखंड: सभी गुणनखंड जो सम हैं (2, 4, 6, 10, 12, 16, 20, 24, 30, 40, 48, 60, 80, 96, 120, 160, 240, 480)
सभी सम गुणनखंडों का योग (सही संस्करण)
long long sumAllEvenFactors(int n) {
if (n % 2 != 0) return 0;
long long sum = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i % 2 == 0) sum += i;
int pair = n / i;
if (pair != i && pair % 2 == 0) sum += pair;
}
}
if (n % 2 == 0) sum += n; // n स्वयं भी गुणनखंड है
return sum;
}उदाहरण: n=12
गुणनखंड: 1, 2, 3, 4, 6, 12 सम गुणनखंड: 2, 4, 6, 12 योग = 24
