今年の一橋大学では素数の個数に関する一行問題が出題され、ちょっとした話題になりました。
$1000$以下の素数は$250$個以下であることを示せ。
（2021年一橋大学 前期第1問）
考え方
極めてシンプルながら良問です。1000以下の素数が250個以下であることを示すには、1000以下の自然数のうち素数でない数が少なくとも750個存在することを示せば十分です。基本的には2の倍数、3の倍数、5の倍数…と素数でない数を数え上げていくことになります。ここでは幾つかの解答例を示します。
解答例
1000以下の自然数のうち、2の倍数は500個、3の倍数は333個、5の倍数は200個、7の倍数は142個存在する。（重複を無視した合計は$1175$）
1000以下の自然数のうち、6の倍数は166個、10の倍数は100個、14の倍数は71個、15の倍数は66個、21の倍数は47個、35の倍数は28個存在する。（重複を無視した合計は$478$）
1000以下の自然数のうち、30の倍数は33個、42の倍数は23個、70の倍数は14個、105の倍数は9個存在する。（重複を無視した合計は$79$）
1000以下の自然数のうち、210の倍数は4個存在する。
以上より、1000以下の自然数のうち、2の倍数または3の倍数または5の倍数または7の倍数となるものの個数は$$1175-478+79-4=772$$となる。したがって素数の候補となる1000以下の自然数の個数は高々 $1000-772=228$ となるから、$1000$以下の素数は$250$個以下であることが示された。
□
上記の解答は「ベン図」の考え方（包除の原理）を利用するもので、本問の模範的な解答と言えます。重複して数えている分の個数は足し引きしなければなりません。ここでケアレスミスをせずに切り抜けられたかが完答できたかどうかのポイントになります。
あるいは、$210$の剰余類で分類することで素数になり得る数の候補を絞り込んでも解答できますが、余りを書き出すのはそれなりに手間です。
別解①
2でも3でも5でも7でも割り切れない正の整数は $210k+r$ と表せる。ここで$k$は整数であり、余り$r$は以下の48個の整数である。
1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209
これより、$k=0,1,2,3$ のとき、$210k+r$ と表せる整数の個数は $4 \times 48 =192$ であり、$k=4$ のときは $1 \leqq r \leqq 160$ の範囲に36個存在する。
これより、1000以下の自然数のうち、$210k+r$ と表せる整数の個数は228個となる。したがって素数の候補となる1000以下の自然数の個数は高々$228$となるから、$1000$以下の素数は$250$個以下であることが示された。
□
2の倍数と3の倍数と5の倍数だけでは合計しても足りないので、他にも合成数が存在することを言えれば証明可能です。この不足分を「チョイ足し」する方法が一番手間の少ない解法かもしれません。
別解②
1000以下の自然数のうち、2の倍数は500個、3の倍数は333個、5の倍数は200個存在する。（重複を無視した合計は$1033$）
1000以下の自然数のうち、6の倍数は166個、10の倍数は100個、15の倍数は66個存在する。（重複を無視した合計は$332$）
1000以下の自然数のうち、30の倍数は33個存在する。
以上より、1000以下の自然数のうち、2の倍数または3の倍数または5の倍数となるものの個数は$$1033-332+33=734$$となる。
また、$31 \times 31 =961 <1000$ より、$7$以上$31$以下の素数（7,11,13,17,19,23,29,31）同士の積（重複を含む）はいずれも$1000$以下であり、それらの個数は全部で ${}_8\mathrm{C}_2+8=36$ である。
よって1000以下の自然数のうち素数でないものの個数は少なくとも $734+36=770$ であるから、素数の候補となる1000以下の自然数の個数は高々 $1000-770=230$ となる。よって$1000$以下の素数は$250$個以下であることが示された。
□
一橋大学の整数問題は通例、第1問に配置されます。本問の解法はほとんどワンパターンなので、はっきり言ってボーナス問題なのですが、ページを開いた瞬間にこの一行問題が目に飛び込んでくると却って焦ってしまうような気もしますね…(笑)。解答を見た後や外野の人間からすると「こんな簡単な問題で試験になるの？」と考えがちですが、こういった受験生の意表を突くタイプの問題は試験本番では案外ふるい落としとして機能するものです。一橋大学の整数問題は発想力が問われる良問の宝庫なので、所詮は文系数学、と胡坐をかいている(？)理系の学生にこそ解いて欲しいですね。
この問題の解答としては、1000以下の素数を一つ一つ数え上げるのは時間が掛かり、筋が悪いと言えるでしょう。素数を数え上げるにしても各素数が実際に素数であることを示す必要があり、解答用紙のスペースも考えると避けるべきです。エラトステネスの篩を描いて示した受験生がいたかどうかは知りませんが、時間の無駄遣いだと思います。
現実的には、1000以下の正の整数のうちで「素数でないもの」が少なくとも750個存在することを示すのが最も自然な選択です。実際に取り組んでみると分かりますが、2の倍数と3の倍数と5の倍数だけでは合計しても734個となり750に微妙に届きません。ここが本問を入試問題たらしめているポイントです。2、3、5の他に7の倍数も考えなくてはならないと後で気付いてガッカリした受験生は多かったのではないでしょうか(笑)
解答例でも確認した通り、1000以下の2、3、5、7の倍数は772個となりますが、7以外の倍数を調べても（あまり意味はありませんが）解答可能です。例えば1000以下の2、3、5、11の倍数は758個となり、2、3、5、13の倍数は754個となります。2、3、5、17の倍数は749個となり、1を加えてギリギリ750個に届きます。
もし問題が「$1000$以下の素数は$200$個以下であることを示せ。」であれば、2、3、5、7、11、13の倍数まで考える必要があり、ベン図方式の解法だとそれなりに手間が掛かります（素数の積を省く別解②と同様の方針なら2、3、5、7の倍数まで数えれば解答可能）。250という数字が本問の難度をちょうど良い塩梅にしています。間違いなく今年の入試問題の目玉と言える問題でした。
実際には$1000$以下の素数は$168$個だけ存在します。詳しくは素数表を参照して下さい。それから完全に余談ですが、素数定理より$$\pi(1000) \approx \dfrac{1000}{\log (1000)} =144.76…$$と概算されます（$\pi(x)$は$x$以下の素数の個数を表す）。$x=10^3$ 程度では結構誤差が大きいですね。
p個の連続した自然数の中に、少なくとも１つのpの倍数が存在する(p:素数)…＊
ここで100以下の素数は、以下の24個…①
2,3,5,7,11,13,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
＊と①より100n+1以上100(n+1)以下範囲に含まれる素数の数は24個より少ない
(n=1,2,3,…,9)
これより1000以下の素数の数は240個以下であり、よって題意は示された
（証明終）
この証明はどうでしょうか
現在受験勉強中ですので不備があれば是非添削お願いします
ふふ譜 さん
コメントありがとうございます。
列挙されているものの中に17が抜けているので、正しくは100以下の素数は「25個」となりますね。
お示しいただいた証明はシンプルな良い別解だと思います。
ひょっとすると作問サイドが想定する解法の一つかもしれません。
命題（＊）は自明としても良さそうですが、時間に余裕があれば簡単に示しておくと良さそうです。（自然数をpで割った余りが 0 ～ p-1 のp通りに限られることを言えばよいでしょう）
受験勉強頑張ってください！