資料結構
網路
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 次瀏覽
廣告