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$ を得る。
$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$ も素数であることがわかる。
参考文献
