किसी संख्या का सबसे बड़ा अभाज्य गुणनखंड ज्ञात करने के लिए C प्रोग्राम?

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