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