エラトステネスの篩を数式で表すと・・・？

素数の一覧表を作るときに、一個一個の数を素数かどうか判定していくのもよいですが、もう少し効率的に行う方法があります。

その方法の一つがエラトステネスの篩（ふるい）です。

エラトステネスの篩は、情報系の大学生であればプログラミングの演習等で一度は実装したことがあるかと思いますが、実に「アルゴリズム的」なものです。説明の際は「手順」を説明されることが多く、私はこれを数式で表そうと考えたことがありませんでした。

ところが、Wikipediaを見ると、エラトステネスの篩はこんな数式で表せると書いてあります。

$\displaystyle \newcommand{\HRNO}{\unicode[sans-serif]{x306E}} \pi(n) - \pi(\sqrt{n}) + 1 = \sum_{d \mid P(\sqrt{n})} \mu(d) \left\lfloor\frac{n}{d}\right\rfloor \tag{1}$

細かい定義は次のとおりですが、本文の中で順に説明していきます。

$\pi(x)$ ： $x$ 以下の素数の個数
$P(z)$ ： $z$ 以下のすべての素数を掛け合わせて得られる数
$\mu(n)$ ：メビウス関数
$\lfloor x \rfloor$ ：ガウス記号（ $x$ を超えない最大の整数）
$a \mid b$ ： $a$ は $b$ を割り切る

こんな風に表せるのか！と驚いた一方で、これはいったいどういうことなんだろうとも思いました。

実際、式 $(1)$ の意味するところは何なのか、初見ではあまりよくわかりません。そこでこの記事では、式 $(1)$ の意味を理解し、どのようにして導かれるのかを理解するために順を追って解説したいと思います。

エラトステネスの篩（復習）

まずはエラトステネスの篩を復習しましょう。エラトステネスの篩は、数の一覧表の中から素数の倍数の数を下から順に篩い落としていき、最終的に残った数を素数と確定する手法です。

ここでは例として100以下の素数を列挙することを考えます。

①まず、1から100までの数を並べます。

この表の数は現在「未確定」の状態になっていますが、以降の手順で「素数である○」「素数ではない×」のいずれかに確定させます。

②表から1を篩い落とします。（つまり1を「素数ではない」として確定させます。）

③表の先頭の数（この場合は2）を「素数である」と確定して、2以外の2の倍数をすべて表から篩い落とします。（つまりこれらの数を「素数ではない」として確定させます。）

④続いて、まだ未確定の数の中から先頭の数（この場合は3）を「素数である」と確定して、3以外の3の倍数をすべて表から篩い落とします。（つまりこれらの数を「素数ではない」として確定させます。）

⑤まだ未確定の数の中から先頭の数（この場合は5）を「素数である」と確定して、5以外の5の倍数をすべて表から篩い落とします。（つまりこれらの数を「素数ではない」として確定させます。）

⑥まだ未確定の数の中から先頭の数（この場合は7）を「素数である」と確定して、7以外の7の倍数をすべて表から篩い落とします。（つまりこれらの数を「素数ではない」として確定させます。）

⑦まだ未確定の数の中から先頭の数（この場合は11）が、 $\sqrt{100} = 10$ を超えたので、未確定の数をすべて「素数である」と確定させます。

これにて、100以下の素数がすべて列挙できました！

集合の要素数で言い換える

エラトステネスの篩の手続きをまとめると、1から $n$ までの $n$ 個の数に対して、そこから $p$ 以外の $p$ の倍数 $2p, 3p, 4p, \ldots$ を篩い落としていくという手法でした。

この手続きは、集合を使って表すと分かりやすいです。

1から $n$ までの自然数の集合を $A$ としましょう。ここで $\# A = n$ です。（ $\#$ は集合の要素数を表す記号です。）

自然数 $k$ に対して、 $A$ の中で $k$ の倍数全体を $A_k$ と表すことにします。たとえば、 $A$ の中の $2$ の倍数全体は $A_2$ と表されます。

$A$ の中で「 $2$ の倍数ではないもの」は、 $A$ から $A_2$ の元を除いた差集合

$A \setminus A_2$

で表すことができます。これがまさに上のエラトステネスの篩の手順③に相当しますね。
（ただし、この場合は 2 を余分に除き過ぎているので、あとで考慮します。）

また、ここからさらに3の倍数を除くと

$A \setminus (A_2 \cup A_3)$

となります。

同様に、 $A$ から $2, 3, 5, 7$ の倍数全体を除いたものは

$A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7)$

となりますね。

$n = 100$ のときは、エラトステネスの篩の手続きはここでストップします。

よって $n = 100$ 以下の素数の個数は、この集合に素数 $2, 3, 5, 7$ （4個）を加えて、 $1$ （1個）を除いたものを考えれば良いことになります。したがって

（100以下の素数の個数） $= \# \{ A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7) \} + 4 - 1$

となります。

ここで、 $n$ 以下の素数の個数を定義しておくと便利ですね。より一般に、実数 $x$ に対して、 $x$ 以下の素数の個数を $\pi(x)$ と定義することにしましょう。

すると

$\pi(100) = \# \{ A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7) \} + 4 - 1$

となります。

右辺の $4$ は $\sqrt{100}$ 以下の素数 $2, 3, 5, 7$ の個数ですので

$\pi(100) = \# \{ A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7) \} + \pi(\sqrt{100}) - 1$

と表しておくとよいでしょう。

移項すると

$\pi(100) - \pi(\sqrt{100}) + 1 = \# \{ A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7) \} \tag{2}$

となります。これはだいぶ式 $(1)$ の形に近づいてきましたね！

ここで

$\# \{ A \setminus (A_2 \cup A_3 \cup A_5 \cup A_7) \} = \# A - \#(A_2 \cup A_3 \cup A_5 \cup A_7)$

ですので、 $\#(A_2 \cup A_3 \cup A_5 \cup A_7)$ を計算できれば良いことになります。

ここで使えるのが包除原理です。

包除原理

一般に集合 $X$ と $Y$ があったときに、 $X \cup Y$ は

$\# (X \cup Y) = \# X + \# Y - \# (X \cap Y)$

と求められます。これが包除原理です。

これはベン図で表すとよく分かります。

$X$ の要素数と $Y$ の要素数を足すと、 $X$ にも $Y$ にも含まれる要素を重複してカウントしていることになりますので、 $\# (X \cap Y)$ を引けば良いというわけですね。

集合が $X, Y, Z$ の3つの場合は

$\begin{align} &\# (X \cup Y \cup Z) \\ &= \# X + \# Y + \# Z \\ &\;\;\;\; - \# (X \cap Y) - \# (Y \cap Z) - \# (Z \cap X) \\ &\;\;\;\; + \# (X \cap Y \cap Z) \end{align}$

となります。

これもベン図を考えるとよく分かります。

$\# X + \# Y + \# Z$ を計算すると、 $X$ と $Y$ 、 $Y$ と $Z$ 、 $Z$ と $X$ の共通部分がそれぞれ重複してカウントされます。そこで、 $\#(X \cap Y) + \# (Y \cap Z) + \# (Z \cap X)$ を引く必要があります。すると、今度は $X, Y, Z$ の全部の共通部分が引かれ過ぎてしまっているので、 $\# (X \cap Y \cap Z)$ を足せばよいというわけです。

そんなわけで、3つの場合の包除原理が証明されます。

集合が3つのケースは

$\begin{align} &\# (X \cup Y \cup Z) \\ &= \text{（個々}\HRNO\text{集合}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; - \text{（2つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; + \text{（3つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \end{align}$

と思うことができます。

これと同じことが $4$ つ以上の場合でも一般に成り立ちます。

$\begin{align} &\# (X_1 \cup X_2 \cup \cdots \cup X_n) \\ &= \text{（個々}\HRNO\text{集合}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; - \text{（2つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; + \text{（3つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; \vdots \\ &\;\;\;\; + (-1)^{n-2} \text{（}n-1\text{個を選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; + (-1)^{n-1} \text{（}n\text{個を選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \end{align}$

したがって、元々の $\# ( A_2 \cup A_3 \cup A_5 \cup A_7 )$ についても

$\begin{align} &\# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \text{（個々}\HRNO\text{集合}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; - \text{（2つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; + \text{（3つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \\ &\;\;\;\; - \text{（4つを選んだ共通部分}\HRNO\text{要素数}\HRNO\text{和）} \end{align}$

と表せるわけです。

すなわち

$\begin{align} &\# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \# A_2 + \# A_3 + \# A_5 + \# A_7 \\ &\;\;\;\; - \#(A_2 \cap A_3) - \#(A_2 \cap A_5) - \#(A_2 \cap A_7) \\ &\;\;\;\;\;\;\;\;\;\;\;\; - \#(A_3 \cap A_5) - \#(A_3 \cap A_7) - \#(A_5 \cap A_7) \\ &\;\;\;\; + \#(A_2 \cap A_3 \cap A_5) + \#(A_2 \cap A_3 \cap A_7) \\ &\;\;\;\;\;\;\;\;\;\;\;\; + \#(A_2 \cap A_5 \cap A_7) + \#(A_3 \cap A_5 \cap A_7) \\ &\;\;\;\; - \#(A_2 \cap A_3 \cap A_5 \cap A_7) \end{align}$

というわけです。

ここで $A_2 \cap A_3$ は「2の倍数かつ3の倍数（なる1以上100以下の整数）」なので $A_2 \cap A_3 = A_6$ です。同様に考えると

$\begin{align} &\# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \# A_2 + \# A_3 + \# A_5 + \# A_7 \\ &\;\;\;\; - \#A_6 - \#A_{10} - \#A_{14} - \#A_{15} - \#A_{21} - \#A_{35} \\ &\;\;\;\; + \#A_{30} + \#A_{42} + \#A_{70} + \#A_{105} \\ &\;\;\;\; - \#A_{210} \end{align}$

が得られます。

あとは、 $\# A_k$ を計算すればよいわけですが、これは100以下の $k$ の倍数の個数なので

$\displaystyle \# A_k = \left\lfloor \frac{100}{k} \right\rfloor$

で表せます。ここで $\lfloor x \rfloor$ はガウス記号（つまり、 $x$ の整数部分）です。

要するに、 $100$ 個の数を下から $k$ 個ずつとっていくと、最大何セット取り除けるかということですね。

したがって

$\begin{align} &\# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \left\lfloor \frac{100}{2} \right\rfloor + \left\lfloor \frac{100}{3} \right\rfloor + \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{7} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{100}{6} \right\rfloor - \left\lfloor \frac{100}{10} \right\rfloor - \left\lfloor \frac{100}{14} \right\rfloor - \left\lfloor \frac{100}{15} \right\rfloor - \left\lfloor \frac{100}{21} \right\rfloor - \left\lfloor \frac{100}{35} \right\rfloor \\ &\;\;\;\; + \left\lfloor \frac{100}{30} \right\rfloor + \left\lfloor \frac{100}{42} \right\rfloor + \left\lfloor \frac{100}{70} \right\rfloor + \left\lfloor \frac{100}{105} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{100}{210} \right\rfloor \end{align} \tag{3}$

が成り立ちます。

式 $(3)$ で計算したのは「2の倍数 or 3の倍数 or 5の倍数 or 7の倍数」の個数なので、実際に計算すべきなのは $\#A$ から上の個数を引いたものになります。

$\# A = 100 = \left\lfloor \frac{100}{1} \right\rfloor$ を使うと

$\begin{align} &\#A - \# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \left\lfloor \frac{100}{1} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{100}{2} \right\rfloor - \left\lfloor \frac{100}{3} \right\rfloor - \left\lfloor \frac{100}{5} \right\rfloor - \left\lfloor \frac{100}{7} \right\rfloor \\ &\;\;\;\; + \left\lfloor \frac{100}{6} \right\rfloor + \left\lfloor \frac{100}{10} \right\rfloor + \left\lfloor \frac{100}{14} \right\rfloor + \left\lfloor \frac{100}{15} \right\rfloor + \left\lfloor \frac{100}{21} \right\rfloor + \left\lfloor \frac{100}{35} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{100}{30} \right\rfloor - \left\lfloor \frac{100}{42} \right\rfloor - \left\lfloor \frac{100}{70} \right\rfloor - \left\lfloor \frac{100}{105} \right\rfloor \\ &\;\;\;\; + \left\lfloor \frac{100}{210} \right\rfloor \end{align} \tag{4}$

が得られます。あとは、これを計算すれば100以下の素数の個数が得られるわけですね。

さて、もうこの式の形は、だいぶ冒頭の式 $(1)$ に近いものになっています。あとはこの符号をどうにかすればよいですね。

ここで

$P(z) = z$ 以下の素数をすべて掛け合わせた数

を導入しましょう。

すると、式 $(4)$ の各項は $\left\lfloor \frac{100}{d} \right\rfloor$ という形の数になっています。この $d$ は、次の2条件を満たす数になっています：

$P(\sqrt{100}) = 2\cdot 3 \cdot 5\cdot 7$ の約数 $d$
$d$ は平方因子を持たない（素因数の指数はすべて1以下）

また、2行目の符号が $-$ 、3行目の符号が $+$ 、・・・と符号が交互に入れ替わっています。

これは $d$ の素因数の個数の偶奇によって決まっています。すなわち、偶数であれば $+$ 、奇数であれば $-$ ということです。

この状況を見事に表す関数があります。それがメビウス関数 $\mu(n)$ です。 $\mu(n)$ は自然数 $n$ に対して次のように定義されます：

$\mu(n) := \begin{cases} (-1)^{w(n)} & (n\, \text{は平方因子を持たない}) \\ 0 & (n\, \text{は平方因子を持つ}) \end{cases} \tag{5}$

ここで $w(n)$ は $n$ の素因子の個数です。

これによって、 $w(n)$ が偶数であれば $(-1)^{w(n)} = +1$ 、 $w(n)$ が奇数であれば $(-1)^{w(n)} = -1$ となり整合するわけです。

これを用いると、式 $(4)$ は次のように書き直せます。

$\begin{align} &\#A - \# (A_2 \cup A_3 \cup A_5 \cup A_7) \\ &= \mu(100) \left\lfloor \frac{100}{1} \right\rfloor \\ &\;\;\;\; + \mu(2) \left\lfloor \frac{100}{2} \right\rfloor + \mu(3) \left\lfloor \frac{100}{3} \right\rfloor + \mu(5) \left\lfloor \frac{100}{5} \right\rfloor + \mu(7) \left\lfloor \frac{100}{7} \right\rfloor \\ &\;\;\;\; + \mu(6) \left\lfloor \frac{100}{6} \right\rfloor + \mu(10) \left\lfloor \frac{100}{10} \right\rfloor + \mu(14) \left\lfloor \frac{100}{14} \right\rfloor \\ &\;\;\;\;\;\;\;\;\;\;\;\; + \mu(15) \left\lfloor \frac{100}{15} \right\rfloor + \mu(21) \left\lfloor \frac{100}{21} \right\rfloor + \mu(35) \left\lfloor \frac{100}{35} \right\rfloor \\ &\;\;\;\; + \mu(30) \left\lfloor \frac{100}{30} \right\rfloor + \mu(42) \left\lfloor \frac{100}{42} \right\rfloor + \mu(70) \left\lfloor \frac{100}{70} \right\rfloor + \mu(105) \left\lfloor \frac{100}{105} \right\rfloor \\ &\;\;\;\; + \mu(210) \left\lfloor \frac{100}{210} \right\rfloor \end{align} \tag{6}$

Σ記号を使ってまとめると

$\displaystyle \#A - \# (A_2 \cup A_3 \cup A_5 \cup A_7) = \sum_{d \mid P(\sqrt{100})} \mu(d) \left\lfloor \frac{100}{d} \right\rfloor \tag{7}$

となります。ここで $d \mid P(z)$ は「 $d$ が $P(z)$ の約数」の意味です。これは平方因子を持たないものも含まれますが、 $d$ が平方因子を持つ場合は $\mu(d) = 0$ になり、その項が消えるのでうまくいくわけですね。

よって

$\displaystyle \pi(100) - \pi(\sqrt{100}) + 1 = \sum_{d \mid P(\sqrt{100})} \mu(d) \left\lfloor \frac{100}{d} \right\rfloor \tag{8}$

が成り立ちます。

ここまでは $n = 100$ として具体的に計算してきましたが、一般の $n$ でも同じ議論ができて、 $100$ をすべて $n$ に置き換えた

$\displaystyle \pi(n) - \pi(\sqrt{n}) + 1 = \sum_{d \mid P(\sqrt{n})} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \tag{1再掲}$

が得られると言うわけです。これでようやく式 $(1)$ が得られました。

お疲れ様です！！

一橋大学の入試

一橋大学で次のような入試問題が出たことがありました。

問題（一橋大学・2021年第1問）

1000以下の素数は250個以下であることを示せ。

この問題は大変話題になったと思いますが、tsujimotterも過去に解いたことがあります。
tsujimotter.hatenablog.com

この解法は「合成数を力技で750個列挙する」という「ウケ狙い」の解法でした。

本来想定される解法は、今回の記事のように包除原理を使うものです。同じ考え方で解けるのでやってみましょう。

まず、 $A$ を「1以上1000以下の整数全体の集合」とします。 $A_k$ を先ほどと同様に「 $A$ の中で $k$ の倍数全体」を表すものとします。

これまでの議論と同様に考えると、 $\sqrt{1000} = 31.62\ldots$ なので $31$ 以下の素数の倍数を $A$ から取り除けば良いことになります。

したがって

$\displaystyle \pi(1000) - \pi(\sqrt{1000}) + 1 = \#\left(A \setminus \left( A_2 \cup A_3 \cup \cdots \cup A_{31} \right) \right)$

を計算すれば良いことになります。

しかしながら、これを包除原理でそのまま計算するのは大変です。

そこで素数 $p = 2, 3, \ldots, 31$ すべてに対して $A_p$ を取り除くのではなく、その中の一部の素数だけを考えます。具体的には、 $p = 2, 3, 5, 7$ に対して、 $A_2, A_3, A_5, A_7$ を取り除くことを考えましょう。すると、取り除く倍数の個数が小さい分、残る数の個数は多くなります。

したがって、次のような不等式が成り立ちます：

$\displaystyle \begin{align} &\pi(1000) - \pi(\sqrt{1000}) + 1 \\ &= \#\left(A \setminus \left( A_2 \cup A_3 \cup \cdots \cup A_{31} \right) \right) \\ &\leq \#\left(A \setminus \left( A_2 \cup A_3 \cup A_{5} \cup A_{7} \right) \right) \end{align}$

あとは右辺を包除原理で計算すればよいでしょう。

$\displaystyle \begin{align} &\#\left(A \setminus \left( A_2 \cup A_3 \cup A_{5} \cup A_{7} \right) \right) \\ &= \left\lfloor \frac{1000}{1} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{1000}{2} \right\rfloor - \left\lfloor \frac{1000}{3} \right\rfloor - \left\lfloor \frac{1000}{5} \right\rfloor - \left\lfloor \frac{1000}{7} \right\rfloor \\ &\;\;\;\; + \left\lfloor \frac{1000}{6} \right\rfloor + \left\lfloor \frac{1000}{10} \right\rfloor + \left\lfloor \frac{1000}{14} \right\rfloor + \left\lfloor \frac{1000}{15} \right\rfloor + \left\lfloor \frac{1000}{21} \right\rfloor + \left\lfloor \frac{1000}{35} \right\rfloor \\ &\;\;\;\; - \left\lfloor \frac{1000}{30} \right\rfloor - \left\lfloor \frac{1000}{42} \right\rfloor - \left\lfloor \frac{1000}{70} \right\rfloor - \left\lfloor \frac{1000}{105} \right\rfloor \\ &\;\;\;\; + \left\lfloor \frac{1000}{210} \right\rfloor \\ &= 1000 \\ &\;\;\;\; - 500 - 333 - 200 - 142 \\ &\;\;\;\; + 166 + 100 + 71 + 66 + 47 + 28 \\ &\;\;\;\; - 33 - 23 - 14 - 9 \\ &\;\;\;\; + 4 \\ &= 228 \end{align}$

$\pi(\sqrt{1000}) = 11$ より

$\pi(1000) \leq 228 + 11 - 1 = 238$

であるので、 $\pi(1000) \leq 1000$ が示されました。

発展：篩法

エラトステネスの篩、思いのほか深くて面白いですね！

今回、エラトステネスの篩を勉強したきっかけは、実は篩法（ふるいほう）の理解のためでした。

せっかく丁寧に説明しましたので、そのエッセンスを少しだけお話しします。

エラトステネスの篩では、 $A = \{1, 2, 3, \ldots, n\}$ として、そこから素数 $2, 3, 5, 7, \ldots$ の倍数全体 $A_2, A_3, A_5, A_7$ を除いて行ったときに残った数の個数を求めるものでした。これは

$\displaystyle \#(A \setminus (\bigcup_{p = 2, 3, 5, 7} A_p)) = \sum_{d \mid 2\cdot 3 \cdot 5 \cdot 7} \mu(d) \,\# A_d$

と表せますね。

より一般に、 $A$ を正の整数の部分集合とします。また、素数の部分集合 $P$ を考えて、実数 $z$ に対して $z$ 以下の $P$ の元全体を $P(z)$ とします。 $P(z)$ の元全体の積を $\Pi(z)$ とします。

このとき、 $P(z)$ 内の素数 $p$ について、 $A$ 内の $p$ の倍数全体 $A_p$ を除いていきます。その残りの個数を $S(A, P, z)$ とおきます。

これは

$\begin{align} S(A, P, z) &= \#(A \setminus (\bigcup_{p \in P(z)} A_p)) \\ &= \sum_{d \,\mid \, \Pi(z)} \mu(d) \,\# A_d \end{align}$

と表せますね。

この $S(A, P, z)$ を計算するさまざまな手法を一般に篩法というそうです。

ところで、包除原理で得られたすべての項を計算することで $S(A, P, z)$ を直接計算できるわけですが、計算すべき項の数が爆発的に大きくなってしまいます。具体的には $P(z)$ の個数 $\# P(z)$ に対して $2^{\# P(z)}$ 個の項が現れることになります。これでは大変ですね。

そこで、 $S(A, P, z)$ をうまく計算する方法が色々提案されていて、ブルンの篩とか、セルバーグの篩といったものが提案されています。

ブルンの篩は、双子素数に関するブルンの定理を証明するのに実際に使われています。

たとえば

$A = \{ n(n+2) \; \mid \; 1 \leq n < x-2 \}$

とします。

$A$ の元 $n(n+2)$ が $p \leq n$ なる素数 $p$ で割り切れるのであれば $n$ か $n+2$ は合成数です。逆に、 $p \leq n$ なる任意の素数 $p$ で割り切れないのであれば $n$ も $n+2$ も素数となり、 $(n, n+2)$ は双子素数となります。