C++でnの階乗（n!）に含まれる素数rの冪を効率的に求める方法

問題の概要

この問題では、2つの整数 n と r が与えられます。求めるのは、n の階乗（n!）に素数 r が何回掛けられているか、つまり素数 r の冪（べき乗の指数）です。

例で理解しよう

入力 − n = 6, r = 2

出力 − 4

説明 −

6! = 6×5×4×3×2×1 = 720
720 = 24 × 32 × 5
したがって、2 の冪は 4

解法アプローチ

素朴な解法とその課題

まず思い浮かぶのは、階乗を実際に計算してから、その値を素数 r で割り続けて冪を求める方法です。しかし、階乗の値は n が少し大きくなるだけで急激に巨大化し、オーバーフローの危険があるため、この方法は実用的とは言えません。

効率的な解法：ルジャンドルの公式

より優れたアプローチは、ルジャンドルの公式（Legendre's formula）を利用することです。この公式を使えば、階乗を計算せずに直接冪を求められます。

n! における r の冪 = ⌊n/r⌋ + ⌊n/r²⌋ + ⌊n/r³⌋ + …

この公式の仕組みは次のとおりです。

• ⌊n/r⌋：1〜n の中に r の倍数がいくつあるかを数えます
• ⌊n/r²⌋：r² の倍数はさらに1つ余分に r を含むため、その分を加算します
• 以降、n/r³、n/r⁴ と続け、商が 1 未満になるまで繰り返します

C++での実装例

上記の解法を実装したプログラムは以下のとおりです。

#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 << "階乗 " << n << " における素数 " << r << " の冪は: " << primePower(n, r);
    return 0;
}

実行結果

階乗 6 における素数 2 の冪は: 4

計算量のポイント

このアルゴリズムの時間計算量は O(log_rn) です。ループの各反復で i が r 倍に増えていくため、反復回数は r を底とする n の対数に比例します。階乗を直接計算する方法と比べて、非常に大きな n に対しても高速に動作するのが大きな利点です。