paizaの「整数Nの約数の個数を数える問題」に挑戦！
最初は「とりあえず1からNまで地道に調べればいいじゃん！」って感じだったけど…。
やってみると、Nが大きくなるとめちゃくちゃ時間かかる！
そこで、問題を整理しつつ賢い解き方を発見したので、まとめた！
問題概要
- 整数 N が与えられる。
- Nの約数の個数を出力せよ。
入力例：
10
出力例：
4
✅ OK例：
const rl = require('readline').createInterface({ input: process.stdin });
let N;
rl.on('line', (input) => {
N = Number(input);
});
rl.on('close', () => {
let count = 0;
for (let i = 1; i <= N; i++) {
if (N % i === 0) {
count++;
}
}
console.log(count);
});
→これでもいいけど、Nが大きくなると計算量がすごいことに…。
💡計算量を減らすには？
一旦整理して考えてみる。
🎯 目標
N の約数の個数を数える。
🔎 基本の方法
- 1 から N までの整数を調べて
- N を割り切れるものがあれば、それは約数。
- 全部数えればOK！
でも、N が大きいと時間がかかる。
だから効率化する方法が
「平方根まで調べる」という考え方。
💡 なぜ平方根まででいい？
約数はペアで出てくるから！
例えば 10 の約数：
- 1 と 10
- 2 と 5
- 3…（残りはない）
小さい方の約数は 1, 2, 3… と並んでいて
大きい方の約数は「10 ÷ 小さい約数」で求められる。
例えば：
- 小さい方 2 → 大きい方 10÷2=5
大きい方と小さい方がペア。
小さい方を見つければ、大きい方も自然にわかる！
つまり、小さい方を調べていって、
「大きい方が小さい方と同じくらいになるところまで」
で十分。
それが 「平方根」🚀
✔️ 例：10 の場合
1 → 10 ÷ 1 = 10
2 → 10 ÷ 2 = 5
3 → 10 ÷ 3 ≈ 3.33（もう同じくらい）
4 → 10 ÷ 4 = 2.5（大きい方が小さい方より小さい）
→ ここから先は「すでに出てきたペアの逆側」なので無視！
✏️ ポイント
- 平方根まで調べれば、約数ペアがすべて見つかる。
- 計算時間がぐっと短くなる（N=100万でも √100万=1000 までで済む）。
✅ OK例：
const rl = require('readline').createInterface({ input: process.stdin });
rl.on('line', (line) => {
const N = Number(line);
let count = 0;
for (let i = 1; i <= Math.sqrt(N); i++) {
if (N % i === 0) {
// 例えば 2×5=10 のようにペアを見つける
// ペアが同じ（例：6×6=36）なら1回、違えば2回数える
count += (i === N / i) ? 1 : 2;
}
}
console.log(count);
});
🌟 まとめ
✅ 1〜Nまで調べるより、平方根までで済む
✅ 「小さい方×大きい方= N」という約数ペアを意識する
✅ これでとっても効率的に約数を数えられる！