इस खंड में, हम देखेंगे कि कैसे हम एक संख्या के सभी विषम अभाज्य गुणनखंडों का योग कुशल तरीके से प्राप्त कर सकते हैं। मान लीजिए 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 √n, 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#include 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; printf("Enter a number: "); scanf("%d", &n); printf("Sum of all odd prime factors: %d", sumOddFactors(n)); }
आउटपुट
Enter a number: 1092 Sum of all odd prime factors: 23
