C++ में भाज्य को विभाजित करने वाली संख्या की अधिकतम घात ज्ञात कीजिए

मान लीजिए कि हमारे पास दो संख्याएँ n और तथ्य हैं। हमें n की सबसे बड़ी घात ज्ञात करनी है, जो तथ्य को विभाजित करती है! (तथ्य का तथ्य)। तो अगर फैक्ट =5, और n =2, तो आउटपुट 3 होगा। तो 5! =120, और यह 2^3 =8 से विभाज्य है।

यहां हम लीजेंड्रे के सूत्र का उपयोग करेंगे। यह प्राइम की सबसे बड़ी शक्ति पाता है, जो तथ्य को विभाजित करता है! हम n के सभी अभाज्य गुणनखंड ज्ञात करेंगे, फिर इसकी सबसे बड़ी घात ज्ञात करेंगे, जो तथ्य को विभाजित करती है!.

अतः यदि तथ्य 146 है, और n =15 है, तो n के अभाज्य गुणनखंड 5 और 3 हैं। अतः

3 के लिए, यह [146/3] + [48/3] + [16/3] + [5/3] + [1/3] =48 + 16 + 5 + 1 + 0 =70 होगा। पी>

5 के लिए, यह [146/5] + [29/5] + [5/5] + [1/3] =29 + 5 + 1 + 0 =35 होगा।

उदाहरण

#include<iostream>
#include<cmath>
using namespace std;
int getPowerPrime(int fact, int p) {
   int res = 0;
   while (fact > 0) {
      res += fact / p;
      fact /= p;
   }
   return res;
}
int findMinPower(int fact, int n) {
   int res = INT_MAX;
   for (int i = 2; i <= sqrt(n); i++) {
      int cnt = 0;
      if (n % i == 0) {
         cnt++;
         n = n / i;
      }
      if (cnt > 0) {
         int curr = getPowerPrime(fact, i) / cnt;
         res = min(res, curr);
      }
   }
   if (n >= 2) {
      int curr = getPowerPrime(fact, n);
      res = min(res, curr);
   }
   return res;
}
int main() {
   int fact = 146, n = 5;
   cout << "Minimum power: " << findMinPower(fact, n);
}

आउटपुट

Minimum power: 35