最新記事 2021年03月25日

テーマ: 算数

素数の個数は何個?

みなさん、こんにちは。受験ドクターの亀井章三です。

今回は中学入試に必要な知識・解法を使って、大学入試の
問題にチャレンジしてみましょう!

さっそく問題です。

問題 1000以下の素数は250個以下であることを示せ
(2021年 一橋大学)

素数とは、1とその数の2個しか約数を持たない数のことです。

2、3,5,7,11、13、17・・・・・・、と最初は書き出すことも可能ですが、
100を超えると、その数が本当に素数なのか確認しながら進めないと
いけませんので大変です。

そこで攻略のポイントは、逆を考える!です。
素数が250個以下である=素数ではない数が750個以上である
ということを示せばOKです。
素数ではない数、ということは何かの倍数(合成数といいます)になって
いることになります。

そこで、小さい素数である2の倍数から考えます。

1から1000までの間に、2の倍数は
1000÷2=500個あります。ただし、2×1=2の2だけは素数に
なりますので、合成数は500-1=499個となります。

次に3の倍数です。
1から1000までの間に3の倍数は
1000÷3=333あまり1より、333個あります。
しかし、この中には先ほど2の倍数のときに数えたものも含まれます。
それを除かないといけません。
それは、2と3の公倍数=2と3の最小公倍数である6の倍数です。
1から1000までの間に6の倍数は
1000÷6=166あまり4より、166個あります。
したがって、333-166-1=166個が新たな合成数となります。
最後に1をひいたのは、3×1=3は素数だからです。
これで合成数は合計499+166=665個となりました。

次は5の倍数です。
1から1000までの間に5の倍数は
1000÷5=200より、200個あります。
しかし、この中には2の倍数と3の倍数のときに数えたものも含まれます。
それを除かないといけません。
5の倍数のうち、2の倍数でも3の倍数でもない数は、
5、25、35、55、65、85・・・、となっておりこれは
30で割ると5か25あまる数です。

そこで周期を使って求めます。
1000÷30=33あまり10
1~30というひとつの周期の中に該当する数は2個あるので、
33回の周期の中では33×2=66個。
最後991~1000の中では、995の1個が該当するので
66+1=67個が、5の倍数であるが2の倍数でも3の倍数でもない数です。
もちろん、最初の5は除くので、67-1=66個が新たな合成数です。
これで合成数は合計665+66=731個となりました。

750個まであとわずかです。
最後は7の倍数で、2でも3でも5でも割り切れない数を19個見つけます。
7の倍数は7×□と表せます。
1から1000までの間の数のとき、1000÷7=142あまり6より、
7×1、7×2、7×3・・・・・7×141、7×142 の142個7の倍数があります。
このうち、2でも3でも5でも割り切れない数は、
□に入る数が2でも3でも5でも割り切れない数ということです。

7×1は除くので、当てはまるのは小さい順に、
7×7、7×11、7×13、7×17、7×19
7×23、7×29、7×31、7×37、7×41
7×43、7×47、7×49、7×53、7×59
7×61、7×67、7×71、7×73
と1000以下で19個見つかりました。
これで合成数は750個となり、750個以上の合成数があることになります。

よって、素数の数は250個以下であることが示されました。

いかがでしたか?この解説には倍数の個数の求め方の様々な解法が
含まれています(ベン図・周期・積を使う)。ぜひ復習してみてください。