इस भाग में, हम देखेंगे कि हम किसी संख्या के सभी विषम अभाज्य गुणनखंडों का योग कुशल तरीके से कैसे प्राप्त कर सकते हैं। एक संख्या n =1092 है, हमें इसके सभी गुणनखंड प्राप्त करने हैं। 1092 के अभाज्य गुणनखंड 2, 2, 3, 7, 13 हैं। सभी विषम कारकों का योग 3+7+13 =23 है। इस समस्या को हल करने के लिए, हमें इस नियम का पालन करना होगा -
- जब संख्या 2 से विभाज्य हो, तो उस कारक को अनदेखा करें, और संख्या को 2 से बार-बार विभाजित करें।
- अब संख्या विषम होनी चाहिए। अब संख्या के 3 से वर्गमूल तक, यदि संख्या वर्तमान मान से विभाज्य है, तो योग के साथ गुणनखंड जोड़ें, और संख्या को वर्तमान संख्या से विभाजित करके संख्या बदलें, फिर जारी रखें।
- आखिरकार, शेष संख्या भी जोड़ दी जाएगी यदि शेष संख्या विषम है
आइए एक बेहतर विचार प्राप्त करने के लिए एल्गोरिथम देखें।
एल्गोरिदम
printPrimeFactors(n): begin sum := 0 while n is divisible by 2, do n := n / 2 done for i := 3 to , increase i by 2, do while n is divisible by i, do sum := sum + i n := n / i done done if n > 2, then if n is odd, then sum := sum + n end if end if end
उदाहरण
#include<iostream>
#include<cmath>
using namespace std;
int sumOddFactors(int n){
int i, sum = 0;
while(n % 2 == 0){
n = n/2; //reduce n by dividing this by 2
}
//as the number is not divisible by 2 anymore, all factors are odd
for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
while(n % i == 0){
sum += i;
n = n/i;
}
}
if(n > 2){
if(n%2 == 1)
sum += n;
}
return sum;
}
main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout <<"Sum of all odd prime factors: "<< sumOddFactors(n);
} आउटपुट
Enter a number: 1092 Sum of all odd prime factors: 23