最後の素因数分解です。2編一気に書いてしまいます(笑)。
4.さらに拡張して、N!の素因数分解を実行するプログラムを考える。
プログラム2の構造は、以下のとおりです。
プログラムはコードだけだと、何をしているのかよくわからないですよね。それを問題の流れと数学の考えから理解しないといけないのは、なかなかの至難の業かもしれません。実際のプログラムでは、仕様書だったり、コメントを合わせて書いておくことで、そのような混乱をしないようにしておくものです。
閑話休題、111~113行は問題文にもあるとおり「Dが素数であるかどうかを判定するため」の処理になっています。112行ですが、もしこの行がなければ、どのような Nも 120行以降の処理に入ってしまいます。ということで、112行では何かしら「はじく処理」が必要です。選択肢を見てもわかるように、
112行は、何か条件に引っかかれば、どこかへ処理を飛ばす。
という処理をおこないます。
112行がなければ、そのまま 120行に行ってしまうので、こちらが「Dが素数のとき」の処理になります。ですので、112行は「Dが素数でなければ、どこかへ処理を飛ばす」処理となります。
Dが素数でないときなので、
- 以降の処理(含まれる Dの個数を数えたり、「Dは何個」と表示すること)はまったく不要です。
- ただ、次の D+1へは処理を引き継がないといけませんから、
飛ばし先は 191行【テ】ということになります。
あとは、「Dが素数でない」を式で表します。Dが素数でないのであれば、2以上 D以下のいずれかの数で割り切れることになります。これを式で表します。
割り切れるということは、余りが 0ということです。つまり、
D÷K=商 あまり 0
ということです、先の説明で INT(D/K)は商ととらえた方がよい。と書きました。それを使えば、
D÷K=INT(D/K)
D=INT(D/K)*K【ツ】
となります。
N=26のときについては、プログラムに当てはめて実行するのではなく、26までの素数を調べることを考えます。この小問の冒頭で「N以下のすべての素数が、N!の素因数として含まれる。」と書いてありますね。
26までの素数を書き下すと、
2, 3, 5, 7, 11, 13, 17, 19, 23
の計 9個があります。このそれぞれについて、結果である 190行が実行されるので、190行は 9回【ト】実行されます。
そして、素因数が 2つだけ含まれている数は、26を割った商が 2となる「11」と「13」の 2回【ナ】だけということになります。
最後に、このプログラムの出力結果は以下のようになります。
N=(26と入力)
素因数2は23個
素因数3は10個
素因数5は6個
素因数7は3個
素因数11は2個
素因数13は2個
素因数17は1個
素因数19は1個
考えている内容はいたってシンプルなのですが、なかなか考えるところもあり、プログラムとしての考え方・とらえ方が必要なところもありのいい問題なのかな?と思いました。