2021 一橋大学[整数]1000以下の素数は250個以下であることを示せ

初めに

まず知識として知っておいて欲しいのが、$100$ 以下の素数は $25$ 個あります。

ざっくりとしたお話になりますが、数が大きくなればなるほど、素数が登場する間隔はどんどん広くなるのはイメージできますか？

ということは、$100$ 以下で素数が $25$ 個あるため、$1000$ 以下では $250$ 個以下であることはざっくりと当たり前のこと。

それを示せという問題です。

最悪全部数え上げるのも１つの手かもしれませんが・・・。

ここでは２通りの解法を紹介します。

解法１

$A$ ： $1000$ 以下の $2$ の倍数

$B$ ： $1000$ 以下の $3$ の倍数

$C$ ： $1000$ 以下の $5$ の倍数　とおく

$n(A\cap B)$ は、$1000$ 以下の $6$ の倍数

$n(B\cap C)$ は、$1000$ 以下の $15$ の倍数

$n(C\cap A)$ は、$1000$ 以下の $10$ の倍数

$n(A\cap B\cap C)$ は、$1000$ 以下の $30$ の倍数

となるので、

$n(A)=500$、$n(B)=333$、$n(C)=200$、$n(A\cap B)=166$、$n(B\cap C)=66$、$n(C\cap A)=100$、$n(A\cap B\cap C)=33$

$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B) -n(B\cap C) -n(C\cap A)+n(A\cap B\cap C)$ より

$n(A\cup B\cup C)=500+333+200-166-66-100+33=734$

この $734$ 個のうち、$2$、$3$、$5$ の $3$ 個は素数であるので、合成数は $731$ 個

上記の合成数は $731$ 個以外の $1000$ 以下の合成数を考えると、

$7\times a$　($a=7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 49 , 53 , 59 , 61 , 67 , 71 , 73$) の $19$ 個が少なくとも存在する．

したがって、少なくとも $731+19=750$ 個の合成数が存在するため、$1000$ 以下の素数の個数は $250$ 個以下である．

解法１の補足

$D$ ： $1000$ 以下の $7$ の倍数

として、$n(A\cup B\cup C\cup D)$ を考えても良い．

しかし、$4$ つの集合はややこしく、$3$ つの集合を考えた。

そして残りが僅か $19$ 個であったので、順に数え上げた。

解法２【オイラー関数の利用】

$1050=2\times3\times 5^2\times 7$ であるので、

$φ(1050)=1050\times \left(1-\displaystyle\frac{1}{2}\right) \times \left(1-\displaystyle\frac{1}{3}\right) \times \left(1-\displaystyle\frac{1}{5}\right) \times \left(1-\displaystyle\frac{1}{7}\right)=240$

これら $240$ 個と、$2$、$3$、$5$、$7$ の $244$ 個以下が $1050$ 以下の素数となる．

オイラー関数については

オイラー関数(ファイ関数)の使い方｜整数・互いに素な自然数の個数

を参考にしてください。