Tìm lũy thừa của số nguyên tố p trong n! trong C ++

Trong bài toán này, chúng ta được cho một số n và một số nguyên tố p. Nhiệm vụ của chúng ta là tìm lũy thừa của số nguyên tố p trong n!

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

Input : n = 6, p = 2
Output : 4

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề này là tìm các giá trị của n !. Và phân tích thừa số nó, và tìm lũy thừa của số nguyên tố p trong phân tích nhân tử.

Ở đây, con số có thể được biểu diễn dưới dạng thừa số lũy thừa của 2 trong 5! =30 là 3.

Giá trị của n giai thừa là

$$ n! \:=\:n ^ * (n-1) ^ * (n-2) ^ * (n-3) \ dotso {^ *} 2 ^ * 1 $$

$$ n! \:=\:3 ^ * 2 ^ * 1 \:=\:6 $$

Lấy n =6 và p =2,

N! =6! =(2 * 3 * 4 * 5 * 6)

N! =720

Hệ số của 720 là 2 * 2 * 2 * 2 * 3 * 3 * 5

Lũy thừa của 2 trong thừa số của 6! là 4.

Do đó đầu ra là 4.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <iostream>
using namespace std;
int powerOfPrimeNfactorial(int N, int P){
   int primePower = 0;
   int factVal = P;
   while (factVal <= N) {
      primePower += N / factVal;
      factVal = factVal * P;
   }
   return primePower;
}
int main(){
   int N = 6;
   int P = 2;
   cout<<"The power of prime number "<<P<<" in "<<N<<"! is "<<powerOfPrimeNfactorial(N, P) << endl;
   return 0;
}

Đầu ra

The power of prime number 2 in 6! is 4