先日までは、第6問(プログラムの問題)を解いていなかったのですが、解いてみるとなかなか面白かったので、解説もどきを以下に書いてみます。内容的には、「素数を絡めた整数問題」として 2次試験でも使えそうな考え方もあります。
N！の素因数分解を考える
問題の主題は、このタイトルにつきます。そこへたどり着くまでの階段として、以下のような順番で進んでいきます。
- 手始めに、6！の素因数分解をやってみる。
- N！に素因数 2がいくつ含まれているのかを考える。
- 同様にして、N！に素因数 5がいくつ含まれているのかを考える。
- さらに拡張して、N！の素因数分解を実行するプログラムを考える。
6！の素因数分解は、中学生でもできるのでここでは説明しません。
2．N！に素因数 2がいくつ含まれているのか
ここは丁寧に考え方が書かれています。文章が長いですが、式を書きながら読み進めれば難しい内容はないと思います。
プログラム 1については、以下のような構造になっています。
- 100：数Nを入力する。
- 110：素因数の 2を変数：Dに格納する。
- 120：素因数 2の個数を Cとし、一度 0にリセットしておく。
- 130：変数：Mに Nの値を格納する。
- 140：この繰り返し操作は、どう頑張っても N回以内には終わる(M＜2になる)はず
- 150：M/Dの整数部分＝Mを Dで割った商を改めて Mとおく。これが 2^Mとして現れる。
- 160：個数：Cに、この Mを加える。
- 170：M＜D(M＜2)になれば、それ以上「操作」はできないので、繰り返しも終了し、190行へ飛ぶ。
- 180：繰り返しの先頭(140行)へ戻る。
- 190：そこまで足し合わせた Cの値を素因数の個数として表示する。
- 200：おわり
INT(X)は、ガウス記号［X］と同じ意味です。そして、INT(M/D)は整数部分というよりも「Mを Dで割った商」ととらえた方が、個数として考えやすいかと思います。
N＝101としたときについては、N＝13のときの例を真似ればいいだけです。
101→ 50 → 25 → 12 → 6 → 3 → 1
太字になっている回数は 6回【オ】であり、これらをすべて足し合わせると最終的な Cの値は、97【カキ】になります。
3．同様にして、N！に素因数 5がいくつ含まれているのかを考える。
素因数が 2から 5に変わるわけですから、110行【クケコ】を D＝5【サ】と置くだけです。割り算も 5で割る操作を繰り返していくことになります。
2014！であれば、
2014 → 402 → 80 → 16 → 3
となり、素因数 5は 501個【シスセ】もつことがわかります。素因数 2の方がこれよりも多くあることは自明なので、2×5＝10で 501回【ソタチ】割れることがわかります。
「2014！には 0がいくつあるのか？(10で何回割り切れるか？)」と聞かれれば、通常は「5の倍数が○個、25の倍数が△個・・・」という要領になりがちですが、このようにして比較的簡単な計算で求めることができます。
ちなみに、N！に対して 0は N/4個未満になることが、ちょっとした計算で求めることができます。2014÷4＝503 あまり 2なので、結構ギリギリですね。
最後の「素因数分解」は、ここまで長くなったので回を分けて書くことにします。
