1000以下の素数は250個以下であることを示せ。
［2021一橋大］
イズミの解答への道
例えば2の倍数を削るだけで、500個（厳密には2は素数なので、499個）削ることができます。3の倍数も削って、5の倍数も削って、とやっていけばかなり削れそうですよね。まずは、ここから発想を得ることができるかがポイントです。
解答
1000以下の整数のうち、2の倍数または3の倍数または5の倍数の個数を求める。
全体集合 U = { n | 1 ≦ n ≦ 1000 , n は自然数} とし、2の倍数の集合をA、3の倍数の集合をB、5の倍数の集合をCとすると、
n(A) = 500 , n(B) = 333 , n(C) = 200 ,
n(A∩B) = 166 , n(B∩C) = 66 , n(A∩C) = 100 ,
n(A∩B∩C) = 33
であるから、求める個数は、
n(A∪B∪C)
= n(A) + n(B) + n(C) – n(A∩B) – n(B∩C) – n(A∩C) + n(A∩B∩C)
= 500 + 333 + 200 – 166 – 66 – 100 + 33 = 734
である。
今求めた734個の数には、素数である 2 , 3 , 5 が含まれているので、これら3つの数を除いた731個は合成数（2 , 3 , 5 を除く、2または3または5の倍数の数）である。
これまでの731個と重複しない、あと19個の素数でない数（1または合成数）として、
1 , 7×7 , 7×11 , 7×13 , 7×17 ,
7×19 , 7×23 , 7×29 , 7×31 , 7×37 ,
7×41 , 7×43 , 7×47 , 7×53 , 7×59 ,
7×61 , 7×67 , 7×71 , 7×73
がある。以上により、750個の素数でない数が挙げられた。
素数は残り250個の中に存在するので、1000以下の素数は250個以下であることが示された。
解説
エラトステネスのふるい
原始的なすべての素数を求める方法として、エラトステネスのふるいというものがある。1
これは、すべての正の整数を書き出したあと、
- 2以外の2の倍数をすべて消す
- 3以外の3の倍数をすべて消す
- 5以外の5の倍数をすべて消す
- ……
今回の問題の解法は、このことを知らなくても思いつくことは難しくないだろうが、この考え方を知っていると、よりこの解法にたどり着きやすいだろう。
オイラー関数を利用した別解
1 , 2 , … , n の中にある n と互いに素な整数の個数を φ(n) と表し、これをオイラー関数とよぶ。
オイラー関数には次の性質が成り立つ。
n の素因数分解が n = pa・qb・rc… と表されるとき、
φ(n) = n ( 1 – 1p ) ( 1 – 1q ) ( 1 – 1r ) …
この事実を用いると、1050 = 2・3・52・7 以下の 1050と互いに素（すなわち 2 , 3 , 5 , 7 と互いに素）な数は、
φ(1050)
= 1050 × ( 1 – 12 ) ( 1 – 13 ) ( 1 – 15 ) ( 1 – 17 )
= 240個
であることが分かる。
この240個の中には素数でないものも存在するが、 2 , 3 , 5 , 7 以外の素数であれば最低限 2 , 3 , 5 , 7 と互いに素でなければならなく、それはこの240個の中にしか存在しない。
すなわち、1050以下の素数は244個以下である（いまの240個に 2 , 3 , 5 , 7 を加えた244個）。
よって、当然1000以下の素数の個数も244個以下であるため、題意が示される。
試験当日のTwitterに、この解法を示したものがありました。当然この方法で解答を作るためには、はじめに示したオイラー関数に関する定理を証明しなければならないが、オイラー関数はちょうど高校数学のギリギリの内容でもあり、これを使うことでよりスマートに解くことができるので紹介することにしました。
なお、オイラー関数については大学入試でも出題されており、一橋大学でも2015年にオイラー関数に関する出題がある。
コメント