Tìm lũy thừa tối đa của một số chia giai thừa trong C ++

Giả sử chúng ta có hai số n và thực tế. Chúng ta phải tìm lũy thừa lớn nhất của n, điều đó chia thực tế! (giai thừa của sự kiện). Vì vậy, nếu fact =5 và n =2, thì đầu ra sẽ là 3. Vì vậy, 5! =120 và số này chia hết cho 2 ^ 3 =8.

Ở đây chúng tôi sẽ sử dụng công thức của Legendre. Điều này tìm thấy lũy thừa lớn nhất của một số nguyên tố, phân chia thực tế !. Chúng ta sẽ tìm tất cả các thừa số nguyên tố của n, sau đó tìm lũy thừa lớn nhất của nó, chia thực tế !.

Vì vậy, nếu thực tế là 146 và n =15, thì các thừa số nguyên tố của n là 5 và 3. Vì vậy

cho 3, nó sẽ là [146/3] + [48/3] + [16/3] + [5/3] + [1/3] =48 + 16 + 5 + 1 + 0 =70.

đối với 5, nó sẽ là [146/5] + [29/5] + [5/5] + [1/3] =29 + 5 + 1 + 0 =35.

Ví dụ

#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);
}

Đầu ra

Minimum power: 35