ei1333's page

ホーム > Wiki

素因数分解

説明

素因数分解する。

計算量

$O(\sqrt N)$

実装例

応用: 約数の個数

ある自然数 $n$ を素因数分解して $n = \prod_{i=1}^r {p_i}^{a_i}$ ($p_i$ は素数) の形で表せたとする。

自然数 $n$ の約数の個数 $d(n)$ は $d(n) = \prod_{i=1}^r (a_i + 1)$ と等しいことが示せる。

問題例