查找在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