1000以下の素数は250個以下である（2021年一橋大学前期数学第1問）

解答例

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$個以下であることが示された。

□

別解①

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$個以下であることが示された。

□

別解②

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$個以下であることが示された。

□