素因数分解 (prime factorization)

概要

1つの数 \(N\) を素因数分解する。

試し割り法 (Trial division) では 2 から \(\lfloor \sqrt{N} \rfloor\) まで試し割りを行い、素因数を求める。

計算量

\(O(\sqrt{N})\)

実装

# N: 素因数分解する数

def factorization(N):
    res = []
    x = N
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

Verified

  • AOJ: "NTL_1_A: Elementary Number Theory - Prime Factorize": source (Python3, 0.02sec)

戻る