篩法:Eratosthenes-Legendreの篩

提供: Mathpedia



$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$ \newcommand{\relmid}[1]{\mathrel{}\middle|\mathrel{}}

本記事では、篩法 (sieve method)の中でも最も古典的な、Eratosthenesの篩と、それに基づいて与えられた数以下の素数の個数を評価したLegendreの篩について解説する。

Eratosthenesの篩

Eratosthenesは、ある範囲の素数をすべて列挙する方法を与えた。

  • $p_1=2$ は素数である。一方で $2$ 自身を除く $2$ の倍数はすべて合成数だから、取り除く。
  • $2$ から先の数で、残った数の中で最小のものである $p_2=3$ は素数である。一方で $3$ 自身を除く $3$ の倍数はすべて合成数だから、取り除く。
  • 以下同様に、 $p_k$ 自身を除く $p_k$ の倍数を取り除いた後に残った数の中で、$p_k$ から先の数で最小のものを $p_{k+1}$ とおいて、

$p_{k+1}$ 自身を除く $p_{k+1}$ の倍数を取り除く。

このようにして、与えられた $k$ に対して、最初の $k$ 個の素数 $p_1=2, p_2=3, \ldots, p_k$ を得る。

例 1

$50$ までの整数 $$\begin{split} & 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \\ & 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, \\ & 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, \\ & 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, \\ & 31, 32, 33, 34, 35, 36, 37, 38, 39, 50\\ \end{split}$$ にEratosthenesの篩を適用する。まず、$2$ は素数なので、$2$ 自身を除く $2$ の倍数を取り除く。 $$\begin{split} & 1, \mathbf{2}, 3, \xcancel{4}, 5, \xcancel{6}, 7, \xcancel{8}, 9, \xcancel{10}, \\ & 11, \xcancel{12}, 13, \xcancel{14}, 15, \xcancel{16}, 17, \xcancel{18}, 19, \xcancel{20}, \ldots, \\ & 21, \xcancel{22}, 23, \xcancel{24}, 25, \xcancel{26}, 27, \xcancel{28}, 29, \xcancel{30}, \ldots, \\ & 31, \xcancel{32}, 33, \xcancel{34}, 35, \xcancel{36}, 37, \xcancel{38}, 39, \xcancel{40}, \ldots, \\ & 41, \xcancel{42}, 43, \xcancel{44}, 45, \xcancel{46}, 47, \xcancel{48}, 49, \xcancel{50}\\ \end{split}$$ $2$ から先に残った数で最小の $3$ が素数なので、$3$ 自身を除く $3$ の倍数を取り除く。 $$\begin{split} & 1, \underline{2}, \mathbf{3}, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \xcancel{9}, \cancel{10}, \\ & 11, \cancel{12}, 13, \cancel{14}, \xcancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\ & \xcancel{21}, \cancel{22}, 23, \cancel{24}, 25, \cancel{26}, \xcancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\ & 31, \cancel{32}, \xcancel{33}, \cancel{34}, 35, \cancel{36}, 37, \cancel{38}, \xcancel{39}, \cancel{40}, \ldots, \\ & 41, \cancel{42}, 43, \cancel{44}, \xcancel{45}, \cancel{46}, 47, \cancel{48}, 49, \cancel{50}\\ \end{split}$$ $3$ から先に残った数で最小の $5$ が素数なので、$5$ 自身を除く $5$ の倍数を取り除く。 $$\begin{split} & 1, \underline{2}, \underline{3}, \cancel{4}, \mathbf{5}, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, \\ & 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\ & \cancel{21}, \cancel{22}, 23, \cancel{24}, \xcancel{25}, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\ & 31, \cancel{32}, \cancel{33}, \cancel{34}, \xcancel{35}, \cancel{36}, 37, \cancel{38}, \cancel{39}, \cancel{40}, \ldots, \\ & 41, \cancel{42}, 43, \cancel{44}, \cancel{45}, \cancel{46}, 47, \cancel{48}, 49, \cancel{50}\\ \end{split}$$ $5$ から先に残った数で最小の $7$ が素数なので、$7$ 自身を除く $7$ の倍数を取り除く。 $$\begin{split} & 1, \underline{2}, \underline{3}, \cancel{4}, \underline{5}, \cancel{6}, \mathbf{7}, \cancel{8}, \cancel{9}, \cancel{10}, \\ & 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\ & \cancel{21}, \cancel{22}, 23, \cancel{24}, \cancel{25}, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\ & 31, \cancel{32}, \cancel{33}, \cancel{34}, \cancel{35}, \cancel{36}, 37, \cancel{38}, \cancel{39}, \cancel{40}, \ldots, \\ & 41, \cancel{42}, 43, \cancel{44}, \cancel{45}, \cancel{46}, 47, \cancel{48}, \xcancel{49}, \cancel{50}\\ \end{split}$$ 残る最初の数は $11$ だから、$11$ までの素数が確かめられる。

また、$49$ 以下の合成数は $\sqrt{49}=7$ 以下の素因数をもたなければならないから、除外されずに残っている $13, 17, \ldots, 47$ も素数であることがわかる。

Legendreの篩

LegendreはEratosthenesの篩をつぎのように変形し、素数の個数を数えることを試みた。 $X$ までの正の整数 $$1, 2, \ldots, X$$ から $\sqrt{X}$ 以下の素数 $p$ で割り切れるものをすべて取り除く。 $n\leq X$ が合成数ならば、$n$ は $\sqrt{n}\leq \sqrt{X}$ 以下の素因数をもつから、取り除かれる。 一方で、$\sqrt{X}$ 以下の素数 $p$ は自分自身で割れるので取り除かれるが、 $\sqrt{X}<p\leq X$ となる素数は、$p$ より小さい素数で割れないから取り除かれずに残る。 よって、取り除かれずに残る数全体は $\sqrt{X}<p\leq X$ となる素数全体と一致する。

つまり $$A=A(X)=\{1, 2, \ldots, \floor{X}\}=\Z\cap [1, X]$$ について $$A_d=\{n\mid n\in A, d\mid n\}$$ を $A$ の要素のうち、$d$ で割り切れるもの全体の集合、 $$S(A, P)=\#\{n\mid n\in A, \gcd(n, P)=1\}$$ を $A$ の要素のうち、$P$ と互いに素なもの、つまり $P$ のどの素因数でも割り切れないもの全体の個数、 $$P(z)=\prod_{p\leq z} p$$ を $z$ 以下の素数の積とすると、$z=\sqrt{X}$ とおけば、 $S(A, P(\sqrt{X}))$ は $A$ の要素のうち、$\sqrt{X}$ 以下の素因数をもたないもの全体の個数となるから、 $$\pi(X)-\pi(\sqrt{X})=S(A, P(\sqrt{X}))$$ となる。

さらに一般に、$z\leq X$ となる実数 $z$ に対して、$p$ が $z$ より大きな素数ならば、$p$ は $z$ より小さな素因数をもたないので $$\pi(X)-\pi(z)\leq S(A, P(z))$$ となる（$p_0$ が $\sqrt{X}$ 以下の最大の素数で、$z$ が $p_0$ より小さいときは、$p_0^2$ は合成数だが、$S(A, P(z))$ に数えられるため、等号は成り立たない）。

$S(A, P(z))$ は $A$ の要素のうち、$z$ 以下の素因数をもたないもの全体の個数となるから、明らかに $$S(A, P(z))=A\backslash \cup_{p\leq z}A_p$$ となる。よって包含と除去の原理より $$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d) \#A_d=\sum_{d\mid P(z)}(-1)^\mu(d)\floor{\frac{X}{d}}$$ となる。$\mu(d)$ はMöbius関数である。

以下、$O^*(f(z))$ は絶対値が $f(z)$ 以下となる量をあらわす。 $$0\leq \frac{X}{d}-\floor{\frac{X}{d}}<1$$ となることから $$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d)\left(\frac{X}{d}+O^*(1)\right)$$ となる。$P(z)$ の約数の個数は $$2^{\omega(P(z))}=2^{\pi(z)}<2^z$$ となる。また $$\sum_{d\mid P(z)}\frac{(-1)^\mu(d)}{d}=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$$ を用いると $$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$ が成り立つ。

$$\prod_{p\leq z}\left(1-\frac{1}{p}\right)^{-1}\geq \sum_{n\leq z}\frac{1}{z}>\log z$$ より $$S(A, P(z))<\frac{X}{\log z}+2^z$$ となるので、 $z=(\log X-\log\log X)/\log 2$ とおくと、 $$\pi(X)\leq z+S(A, P(z))<\frac{X(1+o(1))}{\log\log X}$$ となることがわかる。 とくに、 $$\frac{\pi(X)}{X}\rightarrow 0\ (X\rightarrow\infty)$$ となることが示される。

これは、素数定理はもちろん、初等的かつ比較的容易に得られる結果、たとえば素数の分布（初等的理論）:定理1.1および定理2.2から得られる $$\pi(X)=O\left(\frac{X}{\log X}\right)$$ よりも弱い。和の中の項の個数が $2^z$ 個となって $z$ に比べて大きすぎるためである。

一方で、この考察は $N$ 個の連続する整数 $M+1, M+2, \ldots, M+N$、あるいは 長さ $X$ の区間 $(U, U+X]$ に属する整数にも一般化できる。すなわち $$A=A(X)=\{n\mid U<n\leq U+X\}=\Z\cap (U, X]$$ について $$A_d=\{n\mid n\in A, d\mid n\}$$ とおくと、 $$\abs{\#A_d-\frac{X}{d}}=\abs{\floor{\frac{U+X}{d}}-\floor{\frac{U}{d}}-\frac{U+X}{d}+\frac{U}{d}}<1$$ となるので、上と同様に $$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$ が成り立つ。このことから $z=(\log X-\log\log X)/\log 2$ とおくと、区間 $(U, U+X]$ のとり方によらず $$\pi(U+X)-\pi(U)\leq z+S(A, P(z))<\frac{X}{\log z}+2^z<\frac{X(1+f(X))}{\log\log X}$$ となる関数 $f(X)\rightarrow 0\ (X\rightarrow +\infty)$ が存在することがわかる（Hardy-Littlewood, 1923）。 これは素数定理のみからは従わず、さらにRiemann予想と同値な評価 $$\pi(X)=\mathrm{li} X+O(X^{1/2}\log X)$$ を用いても得られない結果である。

参考文献

  • George Greaves, Sieves in Number Theory, Springer-Verlag, 2001, doi:10.1007/978-3-662-04658-6.
  • Heini Halberstam and Hans Egon-Richert, Sieve Methods, 2nd edition, Dover publications, 2011.
  • G. H. Hardy and J. E. Littlewood, Some problems of Partitio Numeroram; III: On the expression of a number as a sum of primes, Acta. Math. 44 (1923), 1--70.
  • Glyn Harman, Prime-Detecting Sieves, Princeton University Press, 2007.
  • Melvyn B. Nathanson, Additive Number Theory: The Classical Bases, Graduate Texts in Math. 164, Springer-Verlag, 19996, doi:10.1007/978-1-4757-3845-2.
「https://math.jp/w/index.php?title=篩法:Eratosthenes-Legendreの篩&oldid=10064」から取得