素因数分解(prime factorize)

概要

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

計算量

\(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)