読者です 読者をやめる 読者になる 読者になる

理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

2014年センタ試験 数学IIB第6問の解説もどき~その1~

Math Exam

先日までは、第6問(プログラムの問題)を解いていなかったのですが、解いてみるとなかなか面白かったので、解説もどきを以下に書いてみます。内容的には、「素数を絡めた整数問題」として 2次試験でも使えそうな考え方もあります。

 

N!の素因数分解を考える

問題の主題は、このタイトルにつきます。そこへたどり着くまでの階段として、以下のような順番で進んでいきます。

  1. 手始めに、6!の素因数分解をやってみる。
  2. N!に素因数 2がいくつ含まれているのかを考える。
  3. 同様にして、N!に素因数 5がいくつ含まれているのかを考える。
  4. さらに拡張して、N!の素因数分解を実行するプログラムを考える。

6!の素因数分解は、中学生でもできるのでここでは説明しません。

 

2.N!に素因数 2がいくつ含まれているのか

ここは丁寧に考え方が書かれています。文章が長いですが、式を書きながら読み進めれば難しい内容はないと思います。

f:id:miwotukusi:20160515205813p:plain

 

プログラム 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 → 40280 16 3

となり、素因数 5は 501個【シスセ】もつことがわかります。素因数 2の方がこれよりも多くあることは自明なので、2×5=10で 501回【ソタチ】割れることがわかります。

 

「2014!には 0がいくつあるのか?(10で何回割り切れるか?)」と聞かれれば、通常は「5の倍数が○個、25の倍数が△個・・・」という要領になりがちですが、このようにして比較的簡単な計算で求めることができます。

ちなみに、N!に対して 0は N/4個未満になることが、ちょっとした計算で求めることができます。2014÷4=503 あまり 2なので、結構ギリギリですね。

 

最後の「素因数分解」は、ここまで長くなったので回を分けて書くことにします。