平成29年度 I-2-3

解説

この問題で問われていること

Nが素数かどうかを判定する流れ図で、繰り返しを続ける条件(ア)と、素数でないと判定する条件(イ)を選ぶ問題。

解き方

① 素数判定: 2から√Nまでの数で順に割り、1つでも割り切れたら素数でない。√Nを超えても割り切れなければ素数
② 続ける条件(ア)=I≦√N、YESで調べる内容(イ)=NがIで割り切れる
③ ⑤

正解が正しい理由

アルゴリズムは、I=2から順に、I≦√Nの間、NがIで割り切れるかを調べる。(ア)は繰り返しを続ける条件で、I≦√N。真(YES)の場合に(イ)へ進み、NがIで割り切れるなら「素数でない」と表示して終了する。割り切れなければ(NO)、I←I+1として(ア)に戻る。Iが√Nを超えても割り切れる数がなければ、(ア)が偽(NO)となり、「素数である」と表示する。したがってア:I≦√N、イ:NがIで割り切れる、の⑤が正しい。

この問題で必要な基礎

■ なぜ√Nまで調べれば十分なのか
Nが素数でない(2つの数の掛け算で表せる)とき、N=a×bと書くと、aとbの少なくとも一方は√N以下です(両方とも√Nより大きいと、掛けた値がNより大きくなってしまうため)。そのため、2から√Nまでのどの数でも割り切れなければ、Nは素数だと判断できます。

■ 流れ図の読み方
(ア)は「まだ調べる数が残っているか」(真ならもう1回調べる)、(イ)は「今の数Iで割り切れたか」(真なら素数でないと分かる)という判定です。

各選択肢について

• ① アが「I≧√N」、イが「IがNで割り切れる」となっている点が誤り。繰り返しの継続条件はI≦√Nで、割り切れるかどうかはNがIで割り切れるかで判定する。
• ② アが「I≧√N」となっている点、イが「NがIで割り切れない」となっている点が誤り。
• ③ アが「I≧√N」となっている点が誤り。I≧√Nでは、最初のI=2で条件が偽になりやすく、判定が正しく行われない。
• ④ イが「NがIで割り切れない」となっている点が誤り。割り切れないときに「素数でない」と表示するのは逆である。
• ⑤ ア=I≦√N(繰返しの継続条件)、イ=NがIで割り切れる(素数でないと判定する条件)が、アルゴリズムの説明と一致しており、これが正答。

覚えるべきポイント

素数判定では、2以上√N以下の整数で割り切れる数が1つでもあれば素数でなく、1つもなければ素数である。√Nまで調べれば十分な理由は、Nが合成数ならば√N以下の約数を必ず持つためである。