整数の中で１とその数自身の他に約数をもたない数を素数といいます。１以外の整数を２倍した数、３倍した数、・・・は３つ以上の約数があることになるので素数にはなりません。
花子さんは１から１００までの整数にどのような素数があるのかを調べることにしました。１は素数ではないのでまず１を消し、そのあと２以外の２の倍数、３以外の３の倍数、・・・を次々に消していきました。
下の表は３以外の３の倍数までを消していった様子を表しています。これを消せる数がなくなるまで行い、残った数が素数になります。
※ 画像はクリックすると拡大します。
(１)
１から１００までのうち、素数は何個ありますか。
(２)
１から１００までの素数をすべて見つけるためには、( )の倍数までを消せばよい。( )にあてはまる整数を答え、なぜその倍数までを消せばよいのかを説明しなさい。
※ 解説を見る場合は、下の「解説はこちらから」をクリック！
(１)
「２の倍数を消す→３の倍数を消す」という流れだから、次はもちろん４の倍数を消していくんだろうなぁ、と安易に考えちゃダメです(笑)
なぜなら、４の倍数は２の倍数でもあるので、すでに全部消してしまったからです。
というわけで、次は５以外の５の倍数をどんどん消していくと次の図のようになります。
※ 画像はすべて、クリックすると拡大します。
５の倍数を「５×□」と表すと、□に２以上４以下の数を入れた場合の答えは、すでに２や３、４の倍数として消えていました。
※ ５×２＝２×５だから２の倍数、５×３＝３×５だから３の倍数、５×４＝４×５だから４の倍数。
したがって、□に５以上の数をあてはめたときの数の中で、まだ消えていない数に赤い斜線を引きました。
次は６の倍数、ではなく７の倍数を消していきます。６の倍数は２の倍数でもあるので、すでに全部消えていますね。
７の倍数を「７×□」と表すと、□に２以上６以下の数を入れた場合の答えは、すでに２～６の倍数として消えています。
※ ７×２＝２×７だから２の倍数、７×３＝３×７だから３の倍数、７×４＝４×７だから４の倍数、７×５＝５×７だから５の倍数、７×６＝６×７だから６の倍数。
したがって、□に７以上の数をあてはめたときの数の中で、まだ消えていない数に緑色の斜線を引きました。
さて、次は何の倍数を消したらいいのかを考えてみると・・・
・８の倍数はすでに２の倍数として確認済み。
・９の倍数はすでに３の倍数として確認済み。
・１０の倍数はすでに２の倍数として確認済み。
次の１１は素数なのでまだ確認してないのですが、１１の倍数を「１１×□」と表すと、□に２以上１０以下の数を入れたときの答えはすでに全部消してあるはずです。
※ １１×２＝２×１１だから２の倍数、１１×３＝３×１１だから３の倍数、１１×４＝４×１１だから４の倍数、・・・
そこで□に１１以上の数をあてはめてみると、１１×１１＝１２１だから１００を超えてしまいます。
以上から、１から１００までの中にある素数は、次の図の青い○で囲った２５個になります。
(２)
さっきの問題を解いた結果、２から１００までの中にある素数をすべて見つけるためには７の倍数まで消していけばＯＫであることが分かりました。
そこでその理由を簡単にまとめてみると・・・
２から１００までの整数をすべて「□×△」という形で表すと、１００＝１０×１０なので、最終的には１０の倍数まで確認する必要があります。
２の倍数、３の倍数を消した時点で、４の倍数、６の倍数、８の倍数、９の倍数、１０の倍数はすべて消したことになります。
あとは残りの５の倍数と７の倍数をすべて消してしまえば、１００以下の素数の数をすべて見つけることができます。
PR
