查找在C ++中除以阶乘的数字的最大幂
假设我们有两个数字n和事实。我们必须找到n的最大幂，以除以事实！（事实因素）。因此，如果事实=5，并且n=2，则输出将为3。所以5！=120，并且可以被2^3=8整除。
在这里，我们将使用勒让德公式。这找到了质数的最大力量，这分裂了事实！我们将找到n的所有素因子，然后找到n的最大幂，即可除以事实！
因此，如果事实为146，且n=15，则n的素因子为5和3。
对于3，则为[146/3]+[48/3]+[16/3]+[5/3]+[1/3]=48+16+5+1+0=70。
对于5，则为[146/5]+[29/5]+[5/5]+[1/3]=29+5+1+0=35。
示例
#include<iostream>
#include<cmath>
using namespace std;
int getPowerPrime(int fact, int p) {
int res = 0;
while (fact > 0) {
res += fact / p;
fact /= p;
}
return res;
}
int findMinPower(int fact, int n) {
int res = INT_MAX;
for (int i = 2; i <= sqrt(n); i++) {
int cnt = 0;
if (n % i == 0) {
cnt++;
n = n / i;
}
if (cnt > 0) {
int curr = getPowerPrime(fact, i) / cnt;
res = min(res, curr);
}
}
if (n >= 2) {
int curr = getPowerPrime(fact, n);
res = min(res, curr);
}
return res;
}
int main() {
int fact = 146, n = 5;
cout << "Minimum power: " << findMinPower(fact, n);
}输出结果
Minimum power: 35