इस भाग में हम देखेंगे कि कैसे हम किसी संख्या का सबसे बड़ा अभाज्य गुणनखंड एक कुशल तरीके से प्राप्त कर सकते हैं। एक संख्या है मान लीजिए 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 √𝑛, 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<stdio.h>
#include<math.h>
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
