在 C++ 中找到质数 p 在 n! 中的幂

在这个问题中，我们给出数字 n 和质数 p。我们的任务是找到质数 p 在 n! 中的幂

让我们举个例子来理解这个问题，

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

解决方案方法

解决方法很简单，只需找到 n! 的值。然后进行因式分解，并找出分解中质数 p 的幂。

此处，数字可以表示为 5! = 30 中 2 的幂分解 3。

n 阶乘的值是

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

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

不妨设 n = 6，p = 2，

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

n! = 720

720 的因式分解为 2*2*2*2*3*3*5

6! 因式分解中 2 的幂为 4。

因此输出为 4。

示例

演示我们解决方案运行情况的程序

#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;
}

输出

The power of prime number 2 in 6! is 4

更新于： 01-Feb-2022

186 次浏览

开始您的 职业生涯

完成课程以获得认证

开始
广告