センター試験 数学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$ 個もつ。

解説

$6!$ を計算すると
\begin{eqnarray}
6!
&=&
1 \times 2 \times 3 \times 4 \times 5 \times 6 \\
&=&
2 \times 3 \times 2^2 \times 5 \times 2\cdot 3 \\
&=&
2^4 \times 3^2 \times 5 \\
\end{eqnarray}となります。

解答

アイ:42

解答編 つづき

問題

(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で割れるものの個数を求め、次に4でも割れるものの個数を求め、次に8でも割れるものを求め、と繰り返し求めていき、後で個数をすべて足す、という方法をとっています。これをふまえて、次のプログラムの流れを見ていきます。

解答編 つづき

問題

 この手順にしたがって、 $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

解説

まず、プログラムの変数が何を表しているか考えましょう。

Nは入力値なので、素因数分解をしたい数ですね。110行目と190行目からわかるように、Dは素因数です。そして、190行目からわかるように、Cは素因数の個数です。

150行目では、Mを素因数で割った整数部分を求めています。このFOR文で、具体的に素因数の個数を求めていることがわかります。

160行目では、何か変数に設定いるようですが、そもそもプログラム全体を見るとCに代入している記述がないので、ここにはそれが入ることがわかります。Cは素因数の個数が入るんでしたね。上で説明されていた手順を思い出すと、「素因数で割ったときの商の整数部分を、すべて足したもの」が素因数の個数だったので、CはMを足していけばいいことがわかります。よって、ウには2が入ります。

170行目は、190行目に飛ぶための条件です。上で説明されていた手順では、「 $M\lt 2$ となるまで行えばよい」と書かれていました。これ以上2で割れなくなるとき、ということですね。Dが素因数を表していたので、エには3が入ります。

解答

ウエ:23

解答編 つづき

問題

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

解説

プログラムの流れによって、変数がどう変わるか考えてみましょう。

はじめは、J=1 です。150行目で M=50 となり、160行目で C=50 となります。170行目の GOTO は実行されずに、J=2 に移ります。

以下、170行目での変数の値がどうなるかを書き出していくと
 J=2 のとき、 M=25, C=50+25=75
 J=3 のとき、 M=12, C=75+12=87
 J=4 のとき、 M=6, C=87+6=93
 J=5 のとき、 M=3, C=93+3=96
 J=6 のとき、 M=1, C=96+1=97
となり、ここで M<2 が成り立つので、「GOTO 190」が実行されます。よって、J=6 で、 C=97 となります。

解答

オ:6
カキ:97

解答編 つづき

問題

(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

解説

プログラムで、素因数を表しているものはDだったので、これを2から5に書き換えなければいけません。よって、110行目を「LET D=2」から「LET D=5」に変更すればいいですね。

解答

クケコ:110
サ:4

解答編 つづき

問題

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

解説

$2014!$ が素因数 $5$ をいくつもつかは、上で説明されている手順で求められますね。5で割った整数部分を次々に計算して、その和を求めればいいですね。

5で割って整数部分を計算していくと、次のようになります。
 2014 ⇒ 402 ⇒ 80 ⇒ 16 ⇒ 3
この2つ目以降をすべて足したものが求めるものなので\[ 402+80+16+3 = 501 \]となります。

求め方からもわかりますが、素因数 $2$ の個数は、素因数 $5$ の個数よりも多くなります。5で割った整数部分より2で割った整数部分のほうが大きいからです。そのため、 $2014!$ は $5$ で501回割れ、 $2$ でも501回割れます。また、これ以上 $5$ で割れないので、$10$ で割り切れる回数は 501回であることがわかります。

解答

シスセ:501
ソタチ:501

解答編 つづき

問題

(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

解説

120行目以降は、Dが素数のときにだけ実行されなければいけません。そのため、111行から113行では、素数だと判定できたら120行以降に処理が進むようにし、素数でない場合は120行目から190行目までが実行されないようにしなければいけません。

素数であるかどうかは、Dが、「2以上D未満の整数K」で割り切れるかどうかで判断します。選択肢を見ると「INT(D/K)*K」という式がありますが、これがDになっていれば「DはKで割り切れる」、Dでないときは「DはKで割り切れない」を表します。商が整数でない場合は、INT(D/K)は D/K より小さくなるため、K倍しても元には戻りませんが、このことを利用した判定をしています。

すべての「2以上D未満の整数K」について、DがKで割り切れないときに素数だと判定できるため、112行目では、「割り切れれば、素数でない」としなければいけません。処理の途中で判断できるのは、「素数であること」ではなく、「素数でないこと=割り切れること」だからです。そのため、112行目の条件式には、「割り切れること」を表す
 D=INT(D/K)*K
が入り、素数でないとわかったときには、120行目から190行目までを処理しないようにするので、
 GOTO 191
が入ることがわかります。

解答

ツテ:28

解答編 つづき

問題

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

解説

190行は、素因数の種類の数だけ実行されます。 $26!$ を素因数分解したときに含まれる素数の種類は、 $26$ 以下に含まれる素数の種類と等しく、書き出すと\[ 2,3,5,7,11,13,17,19,23 \]の9個あります。なので、190行は9回実行されます。

Cが2となるのは、 $26!$ を素因数分解したときに、素因数が2つとなるときです。素因数をいくつもつかは、素因数で割った整数部分を足していけばいいんでしたね。素因数が $2,3,5,7$ のときは、26を割ったときの整数部分が2を超えるので、Cが2となることはありません。素因数が $11,13$ のときは、26を割ったときの整数部分が2となり、もう一度素因数で割ることができないので、Cは2となります。素因数が $17,19,23$ のときは、26を割ったときの整数部分が1となり、もう一度素因数で割ることができないので、Cは1となります。

以上から、Cが2となるのは、Dが11のときと13のときの、2回だとわかります。

解答

トナ:92