例えば、36の約数の個数は何個でしょうか。

求め方の一つは、約数を一つひとつ書き並べる方法です。
1、2、3、4、6、9、12、18、36の9個です。
これくらいの数であれば、書き出して簡単に求めることができます。

では、例えば、720の約数の個数だと、どうでしょう?

約数を書き並べるには相当の時間がかかりそうです(1と720、2と360、3と240、4と180・・・と、2つずつ求めていったとしても、30近くまで調べていかないといけません)。

こんなとき、素因数分解を利用する方法があります。


素因数分解を利用して約数の個数を求める(1)

720を素因数分解します。

)720
)360
)180
) 90
) 45
) 15
・   5

720=2×2×2×2×3×3×5、720=2^4×3^2×5です。
720


2×2×2×2×3×3×5の因数(約数)の組合せの中から、約数を見つけていきます。

まず、因数(約数)の中から1個だけ取り出すと、2、3、5、それに忘れてはいけないのが1です(1は素数ではないので素因数分解には顔を出していませんが、すべての整数の約数です)。
4個、見つけました。

次に2個取り出すと、2×2、2×3、2×5、3×3、3×5があり、約数は4、6、10、9、15の5個です。

3個取り出すと、2×2×2、2×2×3、2×2×5、2×3×3、2×3×5
、3×3×5であり、8、12、20、18、30、45と6個見つかりました。

4個取り出します。2×2×2×2、2×2×2×3、2×2×2×5、2×2×3×3、2×2×3×5、2×3×3×5と、16、24、40、36、60、90の6個があります。

5個取り出すと、2×2×2×2×3、2×2×2×2×5、2×2×2×3×3、2×2×2×3×5、2×2×3×3×5であり、48、80、72、120、180の5個。

6個取り出すと、2×2×2×2×3×3、2×2×2×2×3×5、2×2×2×3×3×5の3通りで、144、240、360の3個。

最後に7個の約数すべての積、2×2×2×2×3×3×5=720の1個。

4+5+6+6+5+3+1=30個だということになります。

約数2の個数に着目して丁寧に数えたつもりですが、時間もかかるし、結果に自信も持てません。
せっかく素因数分解の結果を使ったのに、もったいないような気がします。

もう少し、効率的なよい方法がないでしょうか。


素因数分解を利用して約数の個数を求める(2)

「場合の数」の考え方を利用してみましょう。

720=2^4×3^2×5でした。
720

因数の一つ、2だけに着目してみます。
2を何個選び取るかを考えると、0個、1個、2個、3個、4個の5通りが考えられます。

3に着目したら、選び取り方は、0個、1個、2個の3通りです。

5に着目すると、5を0個取り出すか、1個取り出すかの2通りです。

例えば、因数の2を0個取り出したとき、3の取り出し方は3通り、そのそれぞれに対して5の取り出し方は2通り、よって3×2の6通りです。

因数2の取り出し方は0、1、2、3、4の5通り。
このそれぞれについて、3の取り出し方3通り×5の取り出し方2通りの、6通りずつがあることになります。

結局、5×3×2=30通り、これで、だいぶ簡単に約数の個数を見つけることができました。

ポイントは、例えば因数が2の4乗のとき、2の選び方を4通りとしないことです。1つも選ばないことも選択できますから、2の選び取り方は、0の1個分を含めた4+1の5通りです。
3の2乗の選び方も2+1の3通り。
5の選び方も1+1の2通り。
1回も選ばない0を数え忘れないことが大切です。


まとめ

例えば、ある数nを素因数分解したとき、x^a×y^bだったとします。
素因数分解と約数の個数


このとき、nの約数の個数は、(a+1)×(b+1)個です。