公務員試験数的処理の分かりやすい解説と問題をの無料オンライン学習サイト

【約数・倍数・素因数分解】問題6

スポンサーリンク

問題

2以上の整数のうち、2の倍数、3の倍数、5の倍数と次々に取り除いていきます。
このように「素数」の倍数を小さい順に取り除いていくと、残った数の中で最も小さい素数でない数は961でした。いくつの倍数まで取り除きましたか。 

  1. 13
  2. 17
  3. 19
  4. 23
  5. 29

想定問題


解答と解説

解答

5

解説

この問題にある操作は、エラストテネスのふるいと呼ばれる、素数全探索アルゴリズムです。

2の倍数、3の倍数、5の倍数まで取り除いたとき、残った数の中で最も小さい素数でない数はいくつなのか考えてみましょう。
考えてわからないときは・・・もちろん書いて調べるのです。
2の倍数、3の倍数まで取り除いたときに残った数の中で最も小さい素数でない数は25ですね。
さらに続けて5の倍数まで取り除いたときはどうですか。
49です。
7×7=49 です。

つまり、取り除いた素数(5)の次の素数(7)の2乗が、残った数の中で最も小さい素数でない数となります。
今回は961が残った数です。
961=31×31 なので、
31の1つ前の素数29が答えです。







スポンサーリンク



→ 問題7 → 数 問題一覧

問題と分かりやすい解説一覧

  • Facebook
  • Hatena
  • twitter
  • Google+

中学数学で穴のある人はこちら

スポンサーリンク

PAGETOP