一橋大学 2021年度 前期文系数学 第1問

$2,3,5,7$ 以外の素数は，$2,3,5,7$ のどれでも割り切れない。したがって，まず $1$ から $1000$ までの整数のうち，これら4数のいずれでも割り切れないものの個数を求める。

1個の数の倍数の個数の和は$$500+333+200+142=1175.$$2個ずつの最小公倍数の倍数の個数の和は$$166+100+71+66+47+28=478.$$3個ずつの場合は$$33+23+14+9=79$$であり，4個すべての最小公倍数 $210$ の倍数は4個である。よって包除原理から，いずれでも割り切れない整数は$$1000-1175+478-79+4=228$$個である。

この228個には $1$ も含まれるが，上からの評価なのでそのまま残してよい。小さい素数 $2,3,5,7$ を加えても，素数の個数は高々$$228+4=232<250$$である。したがって，$1000$ 以下の素数は $250$ 個以下である。

まず $2,3,5$ の倍数である合成数を包除原理で数える。さらに，それらと重ならない合成数として，$7$ 以上 $31$ 以下の素数2個の積を数え，合成数の下界を作る。

$1$ から $1000$ までの整数のうち，$2,3,5$ の少なくとも1つで割り切れるものは，包除原理により$$500+333+200-166-100-66+33=734$$個である。このうち $2,3,5$ 自身を除く731個は合成数である。

次に$$7,11,13,17,19,23,29,31$$の8個の素数から，重複を許して2個を選び，その積を考える。最大でも$${31}^2=961<1000$$であり，積はすべて $1000$ 以下の合成数である。素因数分解の一意性により異なる選び方は異なる整数を与え，その個数は$${}_8{\mathrm{H}}_2={}_9{\mathrm{C}}_2=36$$個である。これらは $2,3,5$ のどれでも割り切れないので，先の731個とは重ならない。

したがって合成数は少なくとも$$731+36=767$$個ある。さらに $1$ は素数でないから，$1000$ 以下の素数の個数は高々$$1000-767-1=232<250$$である。