1.3.1. 素因数分解 (試し割り法)

Code: prime_factorization.py

Test: test_prime_factorization.py

素因数分解とは

素因数分解は、整数 \(n\) を素数の積で表したもの。 例えば \(500\) の素因数分解は

\[500 = 2^2 \times 5^3\]

と表される。右辺に現れる指数の底 \(2,5\) を \(500\) の素因数という。

実装

概要

区間 \([2, \sqrt{n}]\) に含まれる素数を用いて、実際に数を割って素因数とその個数を求める。

\(\sqrt{n}\) 以下の数だけを用いて試し割りすることにより、 \(10^{12}\) 程度の \(n\) に対する素因数分解が可能となる。

実装のポイント

素数リストを使わない方法で実装する。

小さい順に試し割りを行い、素因数を検出する度に、割り切れなくなるまでその素因数で割り続ける。これにより合成数で割られることがなくなる。

計算量

• prime_factorization(n) \(\mathcal{O}(\sqrt{n})\)

コード

from __future__ import annotations
import math


def prime_factorization(n: int) -> tuple[list[int], list[int]]:
    if n == 1:
        return ([1], [1])
    factors = []
    counts = []
    for i in range(2, math.isqrt(n)+1):
        if i * i > n:
            break
        if n % i == 0:
            factors.append(i)
            n //= i
            count = 1
            while n % i == 0:
                n //= i
                count += 1
            counts.append(count)
    if n > 1:
        factors.append(n)
        counts.append(1)
    return factors, counts

使用例

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

2^2 + 5^3