एक अभाज्य संख्या r की घात n में! सी++ में

इस समस्या में, हमें दो पूर्णांक n और r दिए गए हैं। हमारा काम संख्या n के भाज्य में दी गई अभाज्य संख्या r की घात ज्ञात करना है।

आइए समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट - एन =6 आर =2

आउटपुट -4

स्पष्टीकरण -

Factorial n, 6! = 6*5*4*3*2*1 = 720
720 = 24 * 32 * 5, power of 2 is 4

इस समस्या को हल करने के लिए, एक सरल उपाय यह होगा कि सीधे भाज्य ज्ञात किया जाए और फिर अभाज्य संख्या की घात ज्ञात की जाए। लेकिन यह सबसे अच्छा समाधान नहीं है।

एक अन्य कुशल समाधान एक सूत्र का उपयोग कर रहा है,

n में 'r' की शक्ति! =मंजिल(n/r) + मंजिल(n/r2) + मंजिल(n/r3) + ...

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

#include <iostream>
using namespace std;
int primePower(int n, int r) {
   int count = 0;
   for (int i = r; (n / i) >= 1; i = i * r)
      count = count+n/i;
   return count;
}
int main() {
   int n = 6, r = 2;
   cout<<"Power of prime number "<<r<<"in factorial "<<n<<" is : "<<primePower(n, r);
   return 0;
}

आउटपुट

Power of prime number 2in factorial 6 is : 4