质数r在n中的幂!在C ++中

在这个问题上,我们给了两个整数n和r。我们的任务是在数n的阶乘中找到给定质数r的幂。

让我们以一个例子来了解问题

输入-n = 6 r = 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