数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律研究在 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 次浏览
广告