PythonでN=(P!/Q!)を1に減らす最大操作回数を求める方法

問題の概要

2つの整数 P と Q が与えられ、これらから N = P!/Q! という数が作られます。この N を、実行可能な限り多くの操作回数で 1 まで減らすことを考えます。ここでいう1回の操作とは、「N がある整数 X で割り切れるとき、N を N/X に置き換える」というものです。目的は、この操作を行える最大回数を求めることです。

具体例

入力が A = 7、B = 4 の場合を考えてみましょう。このとき N = 7!/4! = 5 × 6 × 7 = 210 となります。

210 を 1 にするには、素因数ごとに順番に割っていくのが最適です。210 = 2 × 3 × 5 × 7 なので、2、3、5、7 の順に4回割ると 1 になり、これ以上操作回数を増やすことはできません。したがって出力は 4 となります。

解法の考え方

N = P!/Q! は (Q+1) × (Q+2) × … × P と分解できます。つまり、必要な操作回数は「Q+1 から P までの各整数が持つ素因数の個数（重複あり）の合計」と一致します。

そこで、あらかじめ各整数の素因数の個数を、エラトステネスの篩に似た動的計画法で一括計算しておき、さらに累積和を取っておきます。こうすれば、任意の a と b に対して答えを O(1) で取り出せるようになります。

アルゴリズムの手順

1. 十分大きなサイズ N（=1000005）の配列 factors を 0 で初期化します。
2. i を 2 から N まで走査します。factors[i] がまだ 0 のままであれば、i は素数です。
3. i が素数なら、i の倍数 j すべてに対して factors[j] = factors[j // i] + 1 と更新します。これは「j ÷ i の素因数の個数に 1 を加える」ことを意味します。各合成数は自身のすべての素因数で順に更新されるため、最終的に正しい素因数の総数が格納されます。
4. factors の累積和を計算します。これで factors[i] は「1 から i までの各数の素因数の総個数」を表すようになります。
5. 答えは factors[a] − factors[b] として返します。これは区間 (b, a] に含まれる整数全体の素因数の総数、すなわち N を 1 にするために必要な最大操作回数に他なりません。

Pythonでの実装例

N = 1000005
factors = [0] * N

def get_prime_facts():
    for i in range(2, N):
        if factors[i] == 0:  # i は素数
            for j in range(i, N, i):
                factors[j] = factors[j // i] + 1
    for i in range(1, N):
        factors[i] += factors[i - 1]

get_prime_facts()
a = 7
b = 4
print(factors[a] - factors[b])

入力

7, 4

出力

4

計算量

前処理（ふるい部分）の時間計算量は O(N log log N)、空間計算量は O(N) です。一度前計算しておけば、以降の各クエリは O(1) で回答できるため、複数の (P, Q) の組み合わせについて答えを求めたい場合にも非常に効率的なアプローチです。