「情報関係基礎」過去問を教材化する：2009素因数分解

　大学入試センター試験「情報関係基礎」2009年のプログラミングの問題は，素因数分解である。これを教材化する。プログラムはPythonで書くが，外部ライブラリをインポートする必要がなく，基本的な知識だけで書ける。
　教材化するに当たっては，次のことを考える。

・問題はWeb上に残っているので検索すれば入手できるが，Web上で
　このように公開するので，問題文そのままは掲載できない。
　そこで，題材だけを借りて，問題文はオリジナルに作り替える。
・実際の授業では，元の問題を解かせてからコーディングだけをPythonで
　やってもよいし，この問題文を参考に，さらに作り替えてもよい。
　そこは生徒の実態に併せて行う。
・コーディングはPythonで行うが，他の言語でもよい。
・コードの中の空欄は，元の問題と同じとは限らない。また，正解は載せない。
　正しくできればちゃんと動くだろう。
・コードの中の空欄は，基本的なことにとどめる。言語の仕様に依存する箇所は
　問題とはしないか説明を加える。

　＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　100以下の数を次のようにして素因数分解する。

手順(1)
　ある数と，その数を割りきることのできる最大の素数を対応させた表を作る。次のような表だ。ただし，98と99の値は空欄にしてある。

手順(2) 
　この表を用いて，たとえば100を素因数分解するには次のようにする。
　　(a) 100 を割り切る最大の素数は，対応表より 5 である。
　　(b) 100を５で割った商を求める。 20になる。
　　(c) 20を割り切る最大の素数は，対応表より 5 である。
　　(d) 20を５で割った商 4 を割り切る最大の素数は，対応表より 2 である。
　　(d) 4を2で割った商 2 を割り切る最大の素数は，対応表より 2 である。
　　(e) 2を2で割った商は１なので，ここで探索を終わる。
　　　　これまでに見つかった「最大の素数」をかければ
　　　　　　100=5×5×2×2
　　　　と素因数分解できる。

問題１
　手順(1) で示した表の，98, 99 に対応する数を求めなさい。

　まずこの対応表を作っていこう。要素の数が101個のリストを用意し，すべての要素を0にしておく。

問題２ 
　このリストを作るために，次のコードを書いた。
1行目で要素が101個のリストを用意している。(02)行目の空欄に正しいものを入れて完成しなさい。なお，左の数は行番号なので打ち込まなくてよい。

(01)  Yakusu = list(range(101))
(02)  for i in range(   ):
(03)      Yakusu[i] = 0

リストYakusu の要素の値を決めて対応表を作る。要素番号０と１は使わないので，２から始める。
２の倍数の番号の要素の値をすべて２にする。

このとき，要素の値が０でない番号３は素数である。3の倍数の番号の要素をすべて3にする。
次に，値が０でない（素数の）５について，同様に行う。

このようにして，２から順に，素数を見つけてその倍数になっている番号の要素の値をその素数で書き換えていく。

問題３
　対応表をつくるプログラムを次のように作った。(05)行目，(07)行目，(09)行目の空欄に適するものを書いてを完成しなさい。

(04)  for i in range(2, 101):
(05)      if Yakusu[i] ==  :
(06)          j = i
(07)          while j <=  :
(08)              Yakusu[j] = i
(09)              j = 

　でき上がったら，問題１で考えた結果を次のコードで確かめなさい。

print(Yakusu[98])
print(Yakusu[99])

問題４
　さらに，問題3のプログラムを確かめるため，素数だけを表示するプログラムを続いて書いた。(11)，(12)行目の空欄に適するものを書いて完成しなさい。なお，(12)行目の end=" " は，print で改行せずに表示するためのものである。改行は13行目で行っている。また，" " は，ダブルクォーテーションと半角スペースである。

(10) for i in range(2, 101):
(11)     if Yakusu[i] ==  :
(12)         print( , end=" ")
(13) print("")

　ここまでできると，次のような値が表示されるはずである。そのようになっていれば正しい。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

問題５
　手順(2) に示したアルゴリズムで，ある数を素因数分解するプログラムを次のように作った。素因数分解する数を k に代入し，(16)行目，(18)行目，(19)行目の空欄に適するものを書いて完成しなさい。

(14) k = 100
(15) print(k, "=", end="")
(16) while :
(17)     print(Yakusu[k], end="")
(18)     k = k // 
(19)     if k >  :
(20)        print("×", end="")

正しくできれば 100 =5×5×2×2 と表示される。
また，kの値を他の値，たとえば 72 にして実行してみよ。

72 =3×3×2×2×2

問題６
　この表を1000まで拡張したものを作り，任意の3桁の数を素因数分解しなさい。たとえば，

　630 =7×5×3×3×2

となる。

================================================

プログラミング実習では，実行してうまくいかなければ間違っているところを探して直す，という作業になるだろう。
しかし，試験の場合はよく考えて一度で正解を得る必要がある。したがって，プログラミングの場合も，よく考えて，場合によっては紙の上でシミュレーションをしてから実際にコーディングする習慣をつけさせたい。