Tìm lũy thừa lớn nhất của một số chia hết giai thừa trong C++

Cho hai số n và fact. Cần tìm lũy thừa lớn nhất của n chia hết fact! (giai thừa của fact). Ví dụ: fact = 5, n = 2, kết quả là 3 vì 5! = 120 chia hết cho 2^3 = 8.

Sử dụng công thức Legendre để tìm lũy thừa lớn nhất của một số nguyên tố chia hết fact!. Ta phân tích n thành các thừa số nguyên tố, sau đó tìm lũy thừa lớn nhất của từng thừa số nguyên tố đó chia fact!, lấy min của các kết quả.

Ví dụ: fact = 146, n = 15. Thừa số nguyên tố của 15 là 3 và 5.

• Với 3: [146/3] + [48/3] + [16/3] + [5/3] + [1/3] = 48 + 16 + 5 + 1 + 0 = 70.
• Với 5: [146/5] + [29/5] + [5/5] + [1/5] = 29 + 5 + 1 + 0 = 35.

Ví dụ

#include <iostream>
#include <cmath>
#include <climits>
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);
}

Kết quả

Minimum power: 35