Tìm số mũ của số nguyên tố p trong n! bằng C++

Mô tả bài toán

Cho n và số nguyên tố p. Tìm số mũ của p trong phân tích thừa số nguyên tố của n! (Legendre's formula).

Ví dụ

n=6, p=2 → 6! = 720 = 2⁴×3²×5 → Output: 4.

Công thức Legendre

Số mũ = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (cho đến khi pᵏ > n).

Mã nguồn C++

#include <iostream>
using namespace std;

int powerOfPrimeNfactorial(int N, int P) {
    int cnt=0;
    for (long long p=P; p<=N; p*=P)
        cnt += N/p;
    return cnt;
}

int main() {
    int N=6, P=2;
    cout << "Power of prime " << P << " in " << N << "! is " << powerOfPrimeNfactorial(N,P);
    return 0;
}

Đầu ra

The power of prime number 2 in 6! is 4