C++で階乗を除算する数の最大累乗を求めます

2つの数nとfactがあるとします。事実を分割するnの最大の累乗を見つけなければなりません！ （事実の階乗）。したがって、fact =5、n =2の場合、出力は3になります。つまり5！ =120であり、これは2 ^ 3=8で割り切れます。

ここでは、ルジャンドルの公式を使用します。これは素数の最大の力を見つけ、それは事実を分割します！。 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