Lũy thừa của một số nguyên tố r trong n! trong C ++

Trong bài toán này, chúng ta có hai số nguyên n và r. Nhiệm vụ của chúng ta là tìm lũy thừa của số nguyên tố r đã cho trong giai thừa của số n.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào - n =6 r =2

Đầu ra - 4

Giải thích -

Factorial n, 6! = 6*5*4*3*2*1 = 720
720 = 24 * 32 * 5, power of 2 is 4

Để giải quyết vấn đề này, một giải pháp đơn giản sẽ là tìm trực tiếp giai thừa và sau đó tìm lũy thừa của số nguyên tố. Nhưng đây không phải là giải pháp tốt nhất.

Một giải pháp hiệu quả khác là sử dụng công thức,

Sức mạnh của ‘r’ trong n! =sàn (n / r) + sàn (n / r2) + sàn (n / r3) + ...

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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<<"Power of prime number "<<r<<"in factorial "<<n<<" is : "<<primePower(n, r);
   return 0;
}

Đầu ra

Power of prime number 2in factorial 6 is : 4