Trong bài toán này, ta được cho hai số nguyên n và r. Nhiệm vụ là tìm số mũ (lũy thừa) của số nguyên tố r trong giai thừa của số n.
Hãy xem ví dụ sau:
Đầu vào – n = 6, r = 2
Đầu ra – 4
Giải thích –
Giai thừa n, 6! = 6*5*4*3*2*1 = 720 720 = 24 * 32 * 5, số mũ của 2 là 4
Để giải bài toán, giải pháp đơn giản là tính trực tiếp giai thừa rồi tìm số mũ của số nguyên tố. Nhưng đây không phải giải pháp tối ưu.
Giải pháp hiệu quả sử dụng công thức:
Số mũ của 'r' trong n! = floor(n/r) + floor(n/r2) + floor(n/r3) + ...
Ví dụ minh họa
Chương trình triển khai giải pháp:
#include <iostream> using namespace std; int primePower(int n, int r) { int count = 0; for (int i = r; (n / i) >= 1; i = i * r) count = count + n/i; return count; } int main() { int n = 6, r = 2; cout<<"Số mũ của số nguyên tố "<<r<<" trong giai thừa "<<n<<" là: "<<primePower(n, r); return 0; }Kết quả
Số mũ của số nguyên tố 2 trong giai thừa 6 là: 4