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

• Z时代
• 2024-01-10
• 分类：综合

在这个问题上，我们给了两个整数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

以上是 质数r在n中的幂！在C ++中 的全部内容， 来源链接： utcz.com/z/322238.html