C++でn!に含まれる素数pの冪指数を求める方法

問題概要

この問題では、数値 n と素数 p が与えられます。求めるのは、n!(nの階乗)に含まれる素数pの冪指数、つまり n! を素因数分解したときに p が何回掛けられているかです。

具体例で確認してみましょう。

入力 : n = 6, p = 2
出力 : 4

この場合、6! = 720 であり、その素因数分解は次のようになります。

720 = 2 × 2 × 2 × 2 × 3 × 3 × 5

2の個数は4つなので、出力は 4 となります。

解決アプローチ(ルジャンドルの公式)

最も単純な解法は、実際に n! の値を計算して素因数分解することですが、n が大きくなると階乗の値は爆発的に増大するため現実的ではありません。

そこで役立つのがルジャンドルの公式(Legendre's formula)です。この公式によると、n! に含まれる素数 p の冪指数は次の式で求められます。

E_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …

これは「n 以下の整数のうち、p の倍数はそれぞれ少なくとも1つの p を寄与し、p² の倍数はさらに1つの p を寄与する…」という考え方に基づいています。

アルゴリズムの手順

1. カウンタ primePower を 0 で初期化します。
2. factVal を p に設定します。
3. factVal ≤ N の間、primePower に N / factVal(整数除算)を加算し、factVal を p 倍します。
4. ループ終了後、primePower を返します。

C++での実装例

上記のアルゴリズムを実装したプログラムがこちらです。

#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

まとめ

このアルゴリズムの計算量は O(log_pN) であり、階乗を直接計算する必要がないため、n が非常に大きい場合でも高速に動作します。競技プログラミングなどで「n! の約数の個数」や「n! を割り切る最大の p 冪」を求める際によく使われるテクニックなので、ぜひ覚えておきましょう。