数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中质数 r 在 n! 中的幂
本题给定两个整数 n 和 r。我们的任务是求出给定质数 r 在数 n 的阶乘中的幂。
举个例子来理解本题
输入 - n = 6 r = 2
输出 - 4
解释 -
Factorial n, 6! = 6*5*4*3*2*1 = 720 720 = 24 * 32 * 5, power of 2 is 4
我们可以通过直接计算阶乘然后求出质数的幂来解决本题。但这并不是最优解。
另一种高效的解法是使用公式，
‘r’ 在 n! 中的幂 = floor(n/r) + floor(n/r2) + floor(n/r3) + ...
示例
展示我们解法实现的程序，
#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; }
输出
Power of prime number 2in factorial 6 is : 4
更新于：2020 年 4 月 17 日
158 次浏览
广告