1.3.2. 素因数分解 (SPF)

Code: prime_factorization.py
Test: test_prime_factorization.py

数表を用いた高速化

\(10^6\) 程度の数に対する素因数分解であれば、数表を用いてクエリ計算量 \(\mathcal{O}(\log{n})\) で求めることができる。

まず、それぞれの数に対する最小の素因数 (Smallest Prime Factor, SPF) を記録した数表を作成する。
数表はエラトステネスの篩と同じ計算量 \(\mathcal{O}(n\log{\log{n}})\) で作成できる。
prime_factorization_spf
素因数分解を求めるには、数に対応する最小の素因数で割ることを繰り返せばよい。
割る過程で通過した最小の素因数を列挙したものが、求めるべき素因数である。

例えば次の例では、 \(12\) の素因数 \(2, 2, 3\) がこの順で得られる。

prime_factorization_12

実装

概要

整数 \(a \in [2, n]\) に対し、その素因数分解を求めるためのテーブルを作成する。

実装のポイント

エラトステネスの篩では、素数かどうかを表すbool値を数表に記録した。
bool値の代わりに最小の素因数を記録することで、最小の素因数の数表を作ることができる。

計算量

  • 前処理

    • list_spf(n) \(\mathcal{O}(n\log{\log{n}})\)

  • クエリ

    • prime_factorization_spf(n) \(\mathcal{O}(\log{n})\)

コード

[1]:

from __future__ import annotations


def list_spf(n: int) -> list[int]:
    spf = [1] * (n+1)
    spf[0] = 0
    spf[1] = 1
    for a in range(2, n+1):
        if spf[a] == 1:
            spf[a] = a
            for i in range(a*a, n+1, a):
                if spf[i] == 1:
                    spf[i] = a
    return spf


def prime_factorization_spf(n: int, spf: list[int]) -> tuple[list[int], list[int]]:
    if n == 1:
        return ([1], [1])
    factors = []
    counts = []
    while n > 1:
        factor = spf[n]
        count = 1
        n //= factor
        while factor == spf[n]:
            count += 1
            n //= factor
        factors.append(factor)
        counts.append(count)
    return factors, counts

使用例

[2]:

spf = list_spf(500)
factors, counts = prime_factorization_spf(500, spf)
print(" + ".join(["{}^{}".format(f, c) for f, c in zip(factors, counts)]))

2^2 + 5^3