इस खंड में, हम देखेंगे कि कैसे हम एक संख्या का सबसे बड़ा अभाज्य गुणनखंड कुशल तरीके से प्राप्त कर सकते हैं। मान लीजिए n = 1092 है, हमें इसका सबसे बड़ा अभाज्य गुणनखंड प्राप्त करना है। 1092 के अभाज्य गुणनखंड 2, 2, 3, 7, 13 हैं। तो सबसे बड़ा 13 है। इस समस्या को हल करने के लिए, हमें इस नियम का पालन करना होगा -
- जब संख्या 2 से विभाज्य हो, तो 2 को सबसे बड़ा के रूप में संग्रहीत करें, और संख्या को बार-बार 2 से विभाजित करें।
- अब संख्या विषम होनी चाहिए। अब 3 से संख्या के वर्गमूल तक, यदि संख्या वर्तमान मान से विभाज्य है, तो गुणनखंड को सबसे बड़ा के रूप में संग्रहीत करें, और संख्या को वर्तमान संख्या से विभाजित करके बदलें फिर जारी रखें।
- और अंत में यदि संख्या 2 से अधिक है, तो यह 1 नहीं है, इसलिए अधिकतम अभाज्य गुणनखंड प्राप्त करें।
आइए एल्गोरिदम देखें ताकि बेहतर विचार मिल सके।
एल्गोरिदम
getMaxPrimeFactors(n)
begin while n is divisible by 2, do max := 2 n := n / 2 done for i := 3 to √n, increase i by 2, do while n is divisible by i, do max := i n := n / i done done if n > 2, then max := n end if end
उदाहरण
#include#include int getMaxPrimeFactor(int n) { int i, max = -1; while(n % 2 == 0) { max = 2; n = n/2; //reduce n by dividing this by 2 } for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers while(n % i == 0) { max = i; n = n/i; } } if(n > 2) { max = n; } return max; } main() { int n; printf("Enter a number: "); scanf("%d", &n); printf("Max prime factor: %d", getMaxPrimeFactor(n)); }
आउटपुट
Enter a number: 24024 Max prime factor: 13
