素因数分解

Nが自然数の2乗で表現できるとき、平方数と言います。

平方数の例4 (= 2×2)
9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム

以下の方法以外にも色々な求め方 ...

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数：

N を素因数分解する
それぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる

素因数分解とは「ある自然数を素数の積の形に分解すること」です。

\(12 = 2^2 × 3\)
\(1024 = 2^{10}\)

1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と ...