数学とクイズでくつろいで＜数学の部屋＜どこよりも遅い！センター試験数学 解説＜情報関係基礎 第３問 解説

どこよりも遅い！情報関連基礎第３問 解説

最終更新日２０１０年８月３日

第３問は２〜１００の整数が素数であるかどうかの判定、および１００の素因数分解を行う手続きの問題。

問１　

　２〜１００の整数のうち、どの数が整数であるかを判別するために以下の手順により判別表を作成する。

  1. 表１のように、２〜１００の番号とそれぞれに対応する値の欄をもつ判別表を用意する。値の欄はすべて０に初期化する。
  2. ０の値を持つ番号のうち、最も小さい番号をｎとする。ｎの倍数の番号に対応する値の欄をすべてｎに書き換える。
  3. 値の欄に０がなくなるまで 2. の手順を繰り返す。

表１

番号２３４５６７８９…979899100
値００００００００…００００

表２

番号２３４５６７８９…979899100
値２０２０２０２０…０２０２

表３

番号２３４５６７８９…979899100
値２３２０３０２３…０２３２

　表１の値の欄で０の値に対応する番号で最も小さい番号は２であるため、２の倍数（２、４、…、１００）の番号に対応する値を２に書き換える。この手続きによって表２の形になる。
　次に表２の値の欄で０の値に対応する番号で最も小さい番号は３である。そのため３の倍数（３、６、…、９９）の番号に対応する値を３に書き換える。この手続きによって表３の形になる。

　この手続きを行うと、値が０で最も小さい番号として素数を小さい順に選ぶことになる。このため、続いて ５の倍数の番号に対応する値の欄を５に書きかえる。さらに続いて ７の倍数の番号に対応する値の欄を７に書きかえる。
　最後に書き換えが行われるのは１００以下の最大の素数である９７の番号に対応する値の欄である。この書き換えで、判別表が完成する。　

表４

番号２３４５６７８９…979899100
値２３２５３７２３…97［オ］［カキ］５

　完成した判別表は上の表４に示すとおりである。このとき各番号に対応する値に入る数はその番号の最大の素数となる。９８＝２×７×７、９９＝３×３×１１　であることから 98 の番号に対応する値の欄には７、99 の番号に対応する値の欄には１１が入る。この判別表において、番号と値とが一致しているものが素数である。

問２．

　問１の手順に基づいて、判別表を作る手続きを作製する。判定表に対応する配列を Yakusu とし、番号は Yakusu の添え字、値は Yakusu の要素で表す。判別表の初期化の手続きは以下の通りである。

(01) i を 2 から 100 まで 1 ずつ増やしながら
(02)　| Yakusu[i] ← 0
(03) を繰り返す

　次に、判別表を作成する手続きは以下の通りである。

(04) i を 2 から 100 まで 1 ずつ増やしながら
　　　| 　（要素が０で添え字が最小のものを探す）
(05)　| 　 もし Yakusu[i] = 0 ならば（解答群の０．）
(06)　| 　　| 　j ← i
　　　| 　　| 　（j から 100 までの添え字の間で操作を行う）
(07)　| 　　| 　　j ≦ 100 の間（解答群の３．）
　　　| 　　| 　（i から i ずつ加えた添え字の要素を i にする）
(08)　| 　　| 　　| 　Yakusu[j] ← i
(09)　| 　　| 　　| 　j ← j+i（解答群の８．）
(10)　| 　　| 　をくり返す
(11)　| 　 を実行する
(12) をくり返す

上の手続きを実行した結果、Yakusu の添え字と要素が一致するものが素数となるため、 素数を判別して印刷する手続きは以下の通りになる。

(01)
　|　Yakusu を初期化する手続き。
(03)
(04)
　|　Yakusu に判別式の値を入れる手続き。
(12)
(13) i を 2 から 100 まで 1 ずつ増やしながら
　　　| 　（添え字と要素が等しいものを探す）
(14)　| 　 もし Yakusu[i] = i ならば（解答群の５．）
　　　| 　　| 　（その要素を印刷する）
(15)　| 　　| 　i を印刷する（解答群の５．）
(16)　| 　を実行する
(17) をくり返す

問３． 素因数分解をするには、商が１になるまで、次々と素数である約数で割っていけばよい。問２で作成した配列 Yakusu の各要素はその添え字の約数の中で最も大きい素数（解答群の１．）が入るため、１００の素因数分解は以下の手続きによって得ることができる。

(01)
　|　Yakusu を初期化する手続き。
(03)
(04)
　|　Yakusu に判別式の値を入れる手続き。
(12)
(13) k ← 100
　　（k が 2 以上である間は手続きを行う）
(14) k > 1 の間（解答群の０．）
　　　| 　（その要素を印刷する）
(15)　| 　Yakusu[k] を印刷する
　　　| 　（添え字が k/Yakusu[k] の要素を調べる）
(16)　| 　k ← k/Yakusu[k]（解答群の３．）
(17) をくり返す

この手続きを行ったときの変数 k の値と印刷される素数を見ると以下の通りになる。

表４

k 100→20→４→２→１
素数５５２２終了

このことから変数 k は 100 の次は 20 となり。手続きの行 (15)（ Yakusu[k] を印刷する）は４回実行される

数学とクイズでくつろいで＜数学の部屋＜どこよりも遅い！センター試験数学 解説＜情報関係基礎 第３問 解説