在 C++ 中查找 n! 中素数 p 的幂
c++server side programmingprogramming更新于 2025/3/15 12:07:17
在这个问题中，我们给出了一个数字 n 和一个素数 p。我们的任务是查找 n! 中素数 p 的幂
让我们举一个例子来理解这个问题，
输入：n = 6，p = 2 输出：4
解决方法
这个问题的一个简单解决方法是简单地找到 n! 的值。然后对其进行因式分解，并在因式分解中找到素数 p 的幂。
在这里，数字可以表示为 5 中 2 的幂因式分解！ = 30 是 3。
n 的阶乘值为
$$n!\:=\:n^*(n-1)^*(n-2)^*(n-3)\dotso{^*}2^*1$$
$$n!\:=\:3^*2^*1\:=\:6$$
设 n = 6 且 p = 2，
n! = 6! = (2*3*4*5*6)
n! = 720
720 的因式分解为 2*2*2*2*3*3*5
6 的因式分解中 2 的幂！是 4。
因此输出是 4。
示例
程序来说明我们的解决方案的工作原理
#include <iostream>
using namespace std;
int powerOfPrimeNfactorial(int N, int P){
int primePower = 0;
int factVal = P;
while (factVal <= N) {
primePower += N / factVal;
factVal = factVal * P;
}
return primePower;
}
int main(){
int N = 6;
int P = 2;
cout<<"<N<<"<<中素数<<<P<<"的幂为<<<powerOfPrimeNfactorial(N, P) << endl;
return 0;
}
输出
6!中素数2的幂为4
