素因数分解 (prime factorization)

概要

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

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

計算量

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

実装

# 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)

Verified

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