nの素数pの累乗を見つけよう！ C++で

この問題では、数nと素数pが与えられます。私たちの仕事は、 nの素数pの累乗を見つけることです！

問題を理解するために例を見てみましょう

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

ソリューションアプローチ

この問題の簡単な解決策は、n！の値を見つけることです。そしてそれを因数分解し、因数分解で素数pの累乗を見つけます。

ここで、数値は5分の2の電力因数分解として表すことができます。 =30は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