今日は「N!（階乗）の中に含まれる2の個数を数える」問題に挑戦！
簡単そうに見えて、実際にやってみたら一筋縄ではいかなくて、なんかプログラミングじゃなくて数学をやってる気分だった…。
今回は僕なりの解き方を丁寧にまとめる＆解説✨
問題概要
N! を 2 で何回割ることができるか？
入力例1
4
出力例1
3
✅ OK例 :
const rl = require('readline').createInterface({ input: process.stdin });
rl.once('line', (input) => {
const N = Number(input);
let count = 0;
for (let i = 2; i <= N; i *= 2) {
count += Math.floor(N / i);
}
console.log(count);
rl.close();
});
一言解説:
2の累乗（2,4,8…）でNを割った商を足していく
🧭 方針：N! の中に含まれる「2」の個数を導く
① N! の中に含まれる「2」の個数を導く理由
僕たちが求めているのは、N!（1×2×3×…×N）を何回「2」で割れるか、
つまり「N! の中に含まれる2の個数」を調べたい！
2の個数が多ければ多いほど、N! は2でたくさん割り切れるってことになるんだ。
だから、2がいくつ含まれているか正確に数える必要がある！
② なぜ “N” を2で割るのか？「割った商」とは何か？
N!（エヌの階乗）というのは、1 × 2 × 3 × … × N までを全部かけた数。
この巨大な数に「2が何回含まれてるか」を調べるのが目的だけど、N! を実際に計算するのは現実的じゃない…。
だって、N=100 とかになると、もう桁がとんでもないことに…。
そこで、N! を作っている「1〜N までの数字」それぞれが、どれだけ「2」を含んでいるかを数え上げるという作戦をとる🚀
つまり、「全部かけた結果を見て2が何個あるか」ではなく、
「2を持ってる数が何個あるかを数えて、合計する」というわけ。
N ÷ 2 で出てくる商は、「2を少なくとも1回含む数」が何個あるかを示す。
たとえば N = 10 のとき、
2, 4, 6, 8, 10 の5つの数が2を含むので、10 ÷ 2 = 5と一致する。
この方法なら、N! を直接計算しなくても、含まれる 2 の数を確実にカウントできる！
だからこそ、N! を作るのではなく、
「N を 2、4、8… で割って商を合計する」方法を使う✨
③ なぜ2だけでなく、2² や 2³ も？
たとえばN=10には：
2の倍数が、2、4、6、8、10 の5個だけど、
注意！
4 は 2²（2×2）なので、「2を2個」含んでいる。
つまり、4は1回じゃなくて 2回カウントする必要がある。
同じように、8 = 2³ は 2を3個持ってるから、
8は「2の1乗」「2の2乗」「2の3乗」の3回分、カウントに入れなきゃいけない！
…というふうに、2の累乗で割っていって、漏れなく全部の「2」を集める必要があるわけ！
だから、
for (let i = 2; i <= N; i *= 2) {
count += Math.floor(N / i);
}
となる。
🗒️ 気づきメモ
- 「2の倍数だけ数える」のは不完全！4や8の分の2を数え漏らすから注意。
- 2の累乗で割って、その商を足すアイデア。
- ループの条件を
i *= 2にするのがポイントで、無駄な計算がない。 -
Math.floorで切り捨てるのも地味に大事。
まとめ
「N!（階乗）」をただ計算するだけじゃなく、その中身を因数分解して分析する視点を持つことが大事だった！
掛け算の結果を見るんじゃなくて、「どんな数が、どれだけ含まれてるか」を見抜く力がつくと、他の問題にも応用できるなと感じた✨
次回は他の解き方にも挑戦！！