スポンサーリンク

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

整数問題

【2021 一橋大学・第1問】

\(1000\) 以下の素数は \(250\) 個以下であることを示せ.

初めに

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

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

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

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

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

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

解法1

\(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\) 個以下である.

解法1の補足

\(D\) : \(1000\) 以下の \(7\) の倍数

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

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

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

実際に \(1000\) 以下の素数を数えると、\(168\) 個です.

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

\(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\) 以下の素数となる.

 

オイラー関数については

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

を参考にしてください。

コメント

タイトルとURLをコピーしました