基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

エラトステネスの篩を用いて2から100までの素数を求めるプログラムを考えます。
以下の疑似コードの空欄に入る適切な式を選んでください。

整数型配列 isPrime[100]
整数型: i, j

for (i ← 1 to 100)
    isPrime[i] ← true
endfor

isPrime[1] ← false

for (i ← 2 to 10)  // 10は√100の整数部分
    if (isPrime[i]) then
        j ← [   ]
        while (j ≦ 100)
            isPrime[j] ← false
            j ← j + i
        endwhile
    endif
endfor

結果として、isPrime[i]がtrueである iの値が2から100までの素数となります。


選択肢：
a) i * 2
b) i * i
c) i + 1
d) i + 2

初めて受験するものです。およそ半年前から勉強を始めました。プログラミングなどの経験はありません。質問ですがこの正解はbだそうですがaも合ってるように思えます。どうなんでしょうか。このくらいわからないと受験きびしいですかね

「エラトステネスの篩」のアルゴリズムを知っているかどうかの問題なので、合否を分けるほどではないと思います。
私もはやしさんの投稿を見て、トレースしてみて「本当だ。aでもbでも求めらる！もしかして出題ミス？」なんて思いました。エラトステネスの篩は知りませんでしたが、合格はできました。
調べてみたところ、
選択肢aでも素数を求めることはできる。
ただし、エラトステネスの篩ではない。
「エラトステネスの篩を用いて」という条件であればbが正解ということのようです。

aとbでは計算量が異なり、
例えば、i=7だとすると
選択肢aだと14からwhile文を回すことになりますが、選択肢bだと49からでよいので回数を減らすことができます。
このプログラムの引数が100ならばあまり差はありませんが、数値が大きくなるほど選択肢aとbの場合で、計算量の差が大きくなるようです。

a,bともに答えは出ますが、計算の回数が違ってきます。

i=2
a)i*2のとき
4,6,8,10・・・
b)i*iのとき
4,6,8,10・・・
同じですが、

i=3
a)のとき
6,9,12,15・・・
b)のとき
9,12,15・・・
＊＊＊6は、i=2のときに、すでにfalseになっているので調べる必要がない。

i=5のとき
a)  10,15,20,25,30・・・
b)  25,30・・・
＊＊＊10,15,20は、i=2,3のときに、すでにfalseになっている。

i=7のとき
a)  14,21,28,35,42,49,56・・・
b)  49,56・・・
＊＊＊14,21,28,35,42は、i=2,3,5のときに、すでにfalseになっている。

プログラムでは、計算量が少ない方がよろしいかと思います。

本試験で、エラトステネスの篩を用いなければ、答えは合ってても計算量的に不正解！のような類の問題は、たぶん今まで１度も見た事ないです。
なんか問題のベクトルがIPAらしくない感じ。
もしこれをあの時間内で正解出来るとなると、700〜800点くらい取れちゃう気がするので、現状なら出来なくても大丈夫かなあと。

まあ2〜3年後のFEとかだと難易度インフレして出るような気もしますがw

皆様ありがとうございます。解説までつけてもらって助かりました。

a,bどちらもエラトステネスの篩と呼べるアルゴリズムにはなると思います。ただ効率がいいアルゴリズムかどうかになるのかと…。選択肢も同じならこの問題は出ないような問題な気がします。サンプル問題では、アルゴリズムの効率よりもアルゴリズムでちゃんと答えが求められるかしか聞いていなかった覚えです。

返信ありがとうございます。この問題はネットのたかいさんの練習問題で見かけました。他にも問題が載っています。自分は普段ペンギンの問題集と参考書で勉強しています。これから受けようと思うのですが自信がありません。

ちょっと余計な話ですが、応用情報の令和６年秋期午後問３に同じアルゴリズムが出ています。興味がおありならご覧になってみてください。

ありがとうございます。是非チェックして学習したいと思います。