スポンサーリンク
問題
２以上の整数のうち、２の倍数、３の倍数、５の倍数と次々に取り除いていきます。
このように「素数」の倍数を小さい順に取り除いていくと、残った数の中で最も小さい素数でない数は961でした。いくつの倍数まで取り除きましたか。
このように「素数」の倍数を小さい順に取り除いていくと、残った数の中で最も小さい素数でない数は961でした。いくつの倍数まで取り除きましたか。
- 13
- 17
- 19
- 23
- 29
想定問題
解答と解説
解答
5
解説
この問題にある操作は、エラストテネスのふるいと呼ばれる、素数全探索アルゴリズムです。
２の倍数、３の倍数、５の倍数まで取り除いたとき、残った数の中で最も小さい素数でない数はいくつなのか考えてみましょう。
考えてわからないときは・・・もちろん書いて調べるのです。
２の倍数、３の倍数まで取り除いたときに残った数の中で最も小さい素数でない数は25ですね。
さらに続けて５の倍数まで取り除いたときはどうですか。
49です。
７×７＝49 です。
つまり、取り除いた素数（５）の次の素数（７）の２乗が、残った数の中で最も小さい素数でない数となります。
今回は961が残った数です。
961＝31×31 なので、
31の１つ前の素数29が答えです。
スポンサーリンク
