なかけんの数学ノート

センター試験 数学II・数学B 2014年度 第6問 解説

【選択問題】(第3問~第6問から2問選択)

問題編

問題

 $\def\myBox#1{\bbox[3px, border:2px solid]{\ \bf{ #1 }\ }}\def\mybox#1{\bbox[4px, border:1px solid gray]{\ #1\ }}$$2$ 以上の自然数 N に対して、 $1$ から N までの自然数の積\[ N! = 1\times 2\times \cdots \times N \]の素因数分解を考える。

(1) $N=6$ のとき、 $N!$ の素因数分解は\[6! =2^{\bbox[1px, border:2px solid]{\ \bf{ ア }\ }}\times 3^{\bbox[1px, border:2px solid]{\ \bf{ イ }\ }} \times 5 \]である。 $6!$ は、素因数 $2$ を $\mybox{ア}$ 個、素因数 $3$ を $\mybox{イ}$ 個、素因数 $5$ を $1$ 個もつ。

(2) $N!$ がもつ素因数 $2$ の個数を求める方法について考えよう。

 まず、 $\displaystyle \frac{N}{2}$ の整数部分を M とおく。 N 以下の自然数の中には、 M 個の偶数 $2,\ 4,\ \cdots,\ 2M$ がある。その他の奇数の積を Q とおくと、 $N!$ は次のように表すことができる。
\begin{eqnarray}
N!
&=&
Q\times 2\times 4\times \cdots \times 2M \\
&=&
Q\times 2^M \times M! \\
\end{eqnarray}したがって、 $N!$ は少なくとも M 個の素因数 $2$ をもつことがわかる。さらに、 $M!$ がもつ素因数 $2$ の個数を求めるために、 $N!$ に対する手順を $M!$ に対して再び用いることができる。

 つまり、 $N!$ がもつ素因数 $2$ の個数を求めるためには、 N から $\displaystyle \frac{N}{2}$ の整数部分である M を求め、 M を改めて N と考えて、同じ手順を用いて新しく M を求める、という手順の繰り返しを $M\lt 2$ となるまで行えばよい。この手順の繰り返しで求められたすべての M の和が、 $N!$ がもつ素因数 $2$ の個数である。

 たとえば、 $N=13$ の場合には、 $\displaystyle \frac{13}{2}=6.5$ であるから、 $M=6$ となる。この手順を繰り返して M を求めた結果は、 N から M を求める手順を矢印 $(\rightarrow)$ で表すと、次のようにまとめられる。\[ 13\rightarrow \mathbf{6} \rightarrow \mathbf{3} \rightarrow \mathbf{1} \]太字で表された $6,3,1$ が、この手順を繰り返して求められた M の値である。それらの和 $6+3+1=10$ が、 $13!$ のもつ素因数 $2$ の個数である。

 この手順にしたがって、 $2$ 以上の自然数 N を入力して、 $N!$ がもつ素因数 $2$ の個数を出力する[プログラム1]を作成した。ただし、INT(X)はXを超えない最大の整数を表す関数である。

[プログラム1]
    100 INPUT PROMPT "N=":N
    110 LET D=2
    120 LET C=0
    130 LET M=N
    140 FOR J=1 TO N
    150     LET M=INT(M/D)
    160     LET 
    170     IF  THEN GOTO 190
    180 NEXT J
    190 PRINT "素因数";D;"は";C;"個"
    200 END

 [プログラム1]の $\myBox{ウ}$ に当てはまるものを、次の 0 ~ 3 のうちから一つ選べ。

 0: C=C+1
 1: C=M
 2: C=C+M
 3: C=C+M+1

 $\myBox{エ}$ に当てはまるものを、次の 0 ~ 4 のうちから一つ選べ。

 0: M>=D
 1: M=D
 2: M<=D
 3: M<D
 3: M>D

 [プログラム1]を実行し、変数N に 101 を入力する。170行の「GOTO 190」が実行されるときの変数J の値は $\myBox{オ}$ である。また、190行で出力される変数C の値は $\myBox{カキ}$ である。

(3) $N!$ がもつ素因数 $2$ の個数を求める方法は、他の素因数の個数についても同様に適用できる。たとえば、 $N!$ がもつ素因数 $5$ を求める場合は、まず、 $\displaystyle \frac{N}{5}$ の整数部分を M とおく。 N 以下の自然数の中には M 個の $5$ の倍数があるので、 $N!$ は少なくとも M 個の素因数 $5$ をもつ。また、これらの M 個の $5$ の倍数を $5$ で割った商は $1,2,\cdots , M$ である。 $M!$ の中の素因数 $5$ の個数を求めるためには、 MN と考えて、同じ手順を繰り返せばよい。

 したがって、 $N!$ がもつ素因数 $5$ の個数を求めるためには、[プログラム1]の $\myBox{クケコ}$ 行を $\myBox{サ}$ に変更すればよい。 $\myBox{サ}$ に当てはまるものを、次の 0 ~ 5 のうちから一つ選べ。

 0: INPUT PROMPT “N=”:N
 1: INPUT PROMPT “C=”:C
 2: INPUT PROMPT “M=”:M
 3: LET C=5
 4: LET D=5
 5: LET M=D

 変更した[プログラム1]を実行することにより、 $2014!$ は素因数 $5$ を $\myBox{シスセ}$ 個もつことがわかる。したがって、 $2014!$ がもつ素因数 $2$ の個数と素因数 $5$ の個数について考えることにより、 $2014!$ を $10$ で割り切れる限り割り続けると、 $\myBox{ソタチ}$ 回割れることがわかる。

(4) N 以下のすべての素数が、 $N!$ の素因数として含まれる。その個数は、素数 $2$ や素数 $5$ の場合と同様に求められる。 N 以下のすべての素因数について、 $N!$ がもつ素因数とその個数を順に出力するように、[プログラム1]を変更して[プログラム2]を作成した。行番号に下線が引かれた行は、変更または追加された行である。
 ただし、繰り返し処理「FOR K=A TO B ~ NEXT K」において、AがBより大きい場合、この繰り返し処理は実行されず次の処理に進む。

[プログラム1]
    100 INPUT PROMPT "N=":N
    110 FOR D=2 TO N
    111     FOR K=2 TO D-1
    112         IF  THEN 
    113     NEXT K
    120     LET C=0
    130     LET M=N
    140     FOR J=1 TO N
    150         LET M=INT(M/D)
    160         LET 
    170         IF  THEN GOTO 190
    180     NEXT J
    190     PRINT "素因数";D;"は";C;"個"
    191 NEXT D
    200 END

 [プログラム2]の111行から113行までの処理は、Dが素数であるかどうかを判定するためのものである。 $\myBox{ツ}$, $\myBox{テ}$ に当てはまるものを、次の 0 ~ 8 のうちから一つずつ選べ。ただし、同じものを選んでもよい。

 0: INT(D/K)=1
 1: INT(D/K)>1
 2: D=INT(D/K)*K
 3: D<>INT(D/K)*K
 4: GOTO 120
 5: GOTO 130
 6: GOTO 180
 7: GOTO 190
 8: GOTO 191

 [プログラム2]を実行し、変数Nに26を入力したとき、190行は $\myBox{ト}$ 回実行される。 $\mybox{ト}$ 回のうち、変数Cの値が2となるのは $\myBox{ナ}$ 回である。

考え方

説明が多くて読むのが大変ですが、階乗の素因数分解の仕方が丁寧に説明されています。説明内容がしっかり理解できていないと、プログラムの処理に落とし込むのは難しいです。

(4)については、素数判定の処理はよく出てくるので見たことがある人も多いはずです。ただ、「割り切れたら」なのか「割り切れなければ」なのかは、処理をよく見ないと判断できません。

次のページへ進む ⇒

[広告]
試験名: 大学入試, センター試験, センターIIB
年度: 2014年度
分野: コンピュータ
トピック: コンピュータ
レベル: ややむずい
キーワード: 素因数分解, プログラム
更新日:2017/01/25