C++에서 계승을 나누는 숫자의 최대 거듭제곱 찾기

두 개의 숫자 n과 사실이 있다고 가정합니다. 사실을 나누는 n의 가장 큰 거듭제곱을 찾아야 합니다! (사실의 요인). 따라서 사실 =5이고 n =2이면 출력은 3이 됩니다. 따라서 5입니다! =120이고 2^3 =8로 나눌 수 있습니다.

여기서는 Legendre 공식을 사용합니다. 이것은 사실을 나누는 소수의 가장 큰 거듭 제곱을 찾습니다!. 우리는 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