【DS検定対策】効率的に数え上げる！「約数の個数」は素因数分解で攻略

データの構造を理解する際、大きな数字を要素ごとに分解して考える手法は非常に重要です。今回は144を題材に、素因数分解を利用して「約数の個数」を機械的に求める方法を解説します。

1. 問題：144の正の約数の個数

【問題】 144の正の約数は、全部で何個あるでしょうか？

① 10個 ② 12個 ③ 15個 ④ 18個

2. 整理：素因数分解（指数の活用）

約数を一つずつ書き出すのは時間がかかります。まずは144を素数の掛け算に分解（素因数分解）し、その「指数（階乗）」に注目するのがコツです。

【世界の切り出し】

[ 144を素因数分解する ]

144 ＝ 12 × 12

    ＝ (2^2 × 3) × (2^2 × 3)

    ＝ 2^4 × 3^2

[ 約数が作られる仕組み ]

約数は、「2を何個使うか」と「3を何個使うか」の組み合わせで決まります。

・2の使い道：{使わない(0個), 1個, 2個, 3個, 4個} の 5通り

・3の使い道：{使わない(0個), 1個, 2個} の 3通り

★ 個数の計算： 5 × 3 ＝ 15個

--------------------------

◎ 公式のイメージ： (指数 ＋ 1) を掛け合わせる

3. 計算プロセス

1. 素因数分解: 144を 2^4 × 3^2 の形にします。
2. 指数に1を足す: 2の指数「4」に1を足して「5」、3の指数「2」に1を足して「3」とします。（※「使わない」という選択肢を1通り加えるためです）
3. 掛け合わせる: 5 × 3 を計算して 15個 となります。

4. DS検定形式：実戦4択クイズ

問：自然数 $N$ が $p^a \times q^b$（$p, q$は素数）と素因数分解されるとき、その正の約数の個数を求める式として正しいものはどれか。

① $a \times b$ ② $(a+1) + (b+1)$ ③ $(a+1) \times (b+1)$ ④ $a^p \times b^q$

【正解： ③ 】

解説： 各素因数について「0個から最大数まで」の選択肢があるため、それぞれの指数に1を足したものを掛け合わせることで、すべての約数の組み合わせ（個数）を網羅できます。

5. まとめ

大きな数字の約数を探すとき、やみくもに割り切れる数字を探すのは非効率です。素因数分解をして「構成要素」を分解することで、今回のように計算だけで確実に個数を導き出せます。データ構造を最小単位まで分解して考える癖をつけましょう！