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