मान लीजिए हमारे पास दो संख्याएं n और fact हैं। हमें n की सबसे बड़ी घात ढूंढनी है, जो fact! (fact का फैक्टोरियल) को विभाजित करती है। इसलिए यदि fact = 5, और n = 2, तो आउटपुट 3 होगा। तो 5! = 120, और यह 2^3 = 8 से विभाज्य है।
यहां हम लेगेंड्रे के सूत्र का उपयोग करेंगे। यह एक अभाज्य संख्या की सबसे बड़ी घात ढूंढता है, जो fact! को विभाजित करती है। हम n के सभी अभाज्य गुणनखंड ढूंढेंगे, फिर उनमें से प्रत्येक की सबसे बड़ी घात ढूंढेंगे जो fact! को विभाजित करती है।
इसलिए यदि fact 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
