C++で階乗を割り切る数の最大の累乗を求める方法

2つの整数 n と fact が与えられたとき、「fact!(fact の階乗)を割り切る n の最大の累乗」を求める問題を考えてみましょう。例えば、fact = 5、n = 2 の場合、答えは 3 になります。これは 5! = 120 であり、120 は 2³ = 8 で割り切れるためです。

ルジャンドルの定理(Legendre's Formula)とは

この問題を効率的に解くには、ルジャンドルの定理を利用します。この定理は「素数 p が fact! を割り切る最大の累乗」を求めるための公式で、次のように表されます。

まず n のすべての素因数を求め、それぞれの素因数について fact! を割り切る最大の累乗を計算します。その中で最小の値が求める答えとなります。

例として、fact = 146、n = 15 の場合を考えてみます。15 を素因数分解すると、素因数は 3 と 5 になります。

素因数 3 の場合:
[146/3] + [48/3] + [16/3] + [5/3] + [1/3] = 48 + 16 + 5 + 1 + 0 = 70

素因数 5 の場合:
[146/5] + [29/5] + [5/5] + [1/5] = 29 + 5 + 1 + 0 = 35

したがって、146! を割り切る 15 の最大の累乗は min(70, 35) = 35 となります。

アルゴリズムの流れ

1. n を素因数分解し、各素因数とその指数(べき乗の数)を求める
2. ルジャンドルの定理を使い、各素因数が fact! を割り切る累乗を計算する
3. 各素因数について「累乗 ÷ 指数」を求め、その最小値を答えとする

C++による実装例

#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

// ルジャンドルの定理:素数 p が fact! を割り切る最大の累乗を求める
int getPowerPrime(int fact, int p) {
    int res = 0;
    while (fact > 0) {
        res += fact / p;
        fact /= p;
    }
    return res;
}

// n が fact! を割り切る最大の累乗を求める
int findMinPower(int fact, int n) {
    int res = INT_MAX;
    for (int i = 2; i <= sqrt(n); i++) {
        int cnt = 0;
        while (n % i == 0) {  // 同じ素因数が連続する場合(べき乗)に対応
            cnt++;
            n = n / i;
        }
        if (cnt > 0) {
            int curr = getPowerPrime(fact, i) / cnt;
            res = min(res, curr);
        }
    }
    if (n >= 2) {  // 残った n が 2 以上なら、それ自体が素因数
        int curr = getPowerPrime(fact, n);
        res = min(res, curr);
    }
    return res;
}

int main() {
    int fact = 146, n = 5;
    cout << "Minimum power: " << findMinPower(fact, n);
}

実行結果

Minimum power: 35

コードの解説

getPowerPrime 関数は、ルジャンドルの定理をそのまま実装したものです。fact を p で割り続け、その商の総和を累積することで、p が fact! を割り切る最大の累乗を求めます。

findMinPower 関数では、2 から √n まで順に試し割りを行って n を素因数分解します。各素因数 i とその指数 cnt が得られたら、getPowerPrime(fact, i) を cnt で割った値を候補とし、最小値を更新していきます。ループ終了後に 2 以上の値が残っていれば、それ自体が素因数であるため同様に処理します。

計算量は、素因数分解に O(√n)、ルジャンドルの定理の計算に O(log_p fact) 必要となるため、全体で非常に効率的に動作します。大きな階乗に対しても高速に答えを求められるのがこの手法の大きな利点です。