1000以下の素数は250個以下である[2021 一橋大]

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年にオイラー関数に関する出題がある。

  1. 古代ギリシアの科学者、エラトステネスが考案したとされている。

コメント

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