センター試験 数学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$ の個数を求めるためには、 M を N と考えて、同じ手順を繰り返せばよい。

　したがって、 $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)については、素数判定の処理はよく出てくるので見たことがある人も多いはずです。ただ、「割り切れたら」なのか「割り切れなければ」なのかは、処理をよく見ないと判断できません。

---

【選択問題】(第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$ の個数を求めるためには、 M を N と考えて、同じ手順を繰り返せばよい。

　したがって、 $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