エラトステネスの篩

エラトステネスの篩(ふるい)とは、
指定された整数以下の素数を全て取り出すことのできる、単純ですが強力な手法です。

手順は次の通りです。

1. 1を消す。
2. 2以外の2の倍数を消す。
3. 3以外の3の倍数を消す。
4. 以下、同様。p以外のpの倍数を消す。
5. が指定の整数を超えたら、4の手順を実施せずに終了。

本稿では、120までの素数を、エラトステネスの篩を用いて篩出していきましょう。

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline
21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ \hline
31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ \hline
41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ \hline
51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ \hline
61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ \hline
71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ \hline
81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ \hline
91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \\ \hline
101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & 109 & 110 \\ \hline
111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 \\ \hline
\end{array}

ステップ1: 1を消す

まず、1は素数ではないので、消します。
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline
21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ \hline
31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ \hline
41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ \hline
51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ \hline
61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ \hline
71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ \hline
81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ \hline
91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \\ \hline
101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & 109 & 110 \\ \hline
111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 \\ \hline
\end{array}

ステップ2: 2以外の2の倍数を消す

2を除き、2の倍数を消します。
この手順で、2×某となる数を消すことができます。
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
& \underline{2} & 3 && 5 && 7 && 9 & \\ \hline
11 &\ \ \ \ \ \ & 13 &\ \ \ \ \ \ & 15 &\ \ \ \ \ \ & 17 &\ \ \ \ \ \ & 19 &\ \ \ \ \ \ \ \\ \hline
21 && 23 && 25 && 27 && 29 & \\ \hline
31 && 33 && 35 && 37 && 39 & \\ \hline
41 && 43 && 45 && 47 && 49 & \\ \hline
51 && 53 && 55 && 57 && 59 & \\ \hline
61 && 63 && 65 && 67 && 69 & \\ \hline
71 && 73 && 75 && 77 && 79 & \\ \hline
81 && 83 && 85 && 87 && 89 & \\ \hline
91 && 93 && 95 && 97 && 99 & \\ \hline
101 && 103 && 105 && 107 && 109 & \\ \hline
111 && 113 && 115 && 117 && 119 & \\ \hline
\end{array}

ステップ3: 3以外の3の倍数を消す

3を除き、3の倍数を消します。
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
& \underline{2} & \underline{3} && 5 && 7 &&& \\ \hline
11 &\ \ \ \ \ \ & 13 &\ \ \ \ \ \ &&\ \ \ \ \ \ & 17 &\ \ \ \ \ \ & 19 &\ \ \ \ \ \ \ \\ \hline
&& 23 && 25 &&&& 29 & \\ \hline
31 &&&& 35 && 37 &&& \\ \hline
41 && 43 &&&& 47 && 49 & \\ \hline
&& 53 && 55 &&&& 59 & \\ \hline
61 &&&& 65 && 67 &&& \\ \hline
71 && 73 &&&& 77 && 79 & \\ \hline
&& 83 && 85 &&&& 89 & \\ \hline
91 &&&& 95 && 97 &&& \\ \hline
101 && 103 &&&& 107 && 109 & \\ \hline
&& 113 && 115 &&&& 119 & \\ \hline
\end{array}

ステップ4: 5以外の5の倍数を消す

4は既に消えているので、次は5です。
5を除き、5の倍数を消します。
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
& \underline{2} & \underline{3} && \underline{5} && 7 &&& \\ \hline
11 &\ \ \ \ \ \ & 13 &\ \ \ \ \ \ &\ \ \ \ \ \ &\ \ \ \ \ \ & 17 &\ \ \ \ \ \ & 19 &\ \ \ \ \ \ \ \\ \hline
&& 23 &&&&&& 29 & \\ \hline
31 &&&&&& 37 &&& \\ \hline
41 && 43 &&&& 47 && 49 & \\ \hline
&& 53 &&&&&& 59 & \\ \hline
61 &&&&&& 67 &&& \\ \hline
71 && 73 &&&& 77 && 79 & \\ \hline
&& 83 &&&&&& 89 & \\ \hline
91 &&&&&& 97 &&& \\ \hline
101 && 103 &&&& 107 && 109 & \\ \hline
&& 113 &&&&&& 119 & \\ \hline
\end{array}

ステップ5: 7以外の7の倍数を消す

7を除き、7の倍数を消します。
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
& \underline{2} & \underline{3} && \underline{5} && \underline{7} &&& \\ \hline
11 &\ \ \ \ \ \ & 13 &\ \ \ \ \ \ &\ \ \ \ \ \ &\ \ \ \ \ \ & 17 &\ \ \ \ \ \ & 19 &\ \ \ \ \ \ \ \\ \hline
&& 23 &&&&&& 29 & \\ \hline
31 &&&&&& 37 &&& \\ \hline
41 && 43 &&&& 47 &&& \\ \hline
&& 53 &&&&&& 59 & \\ \hline
61 &&&&&& 67 &&& \\ \hline
71 && 73 &&&&&& 79 & \\ \hline
&& 83 &&&&&& 89 & \\ \hline
&&&&&& 97 &&& \\ \hline
101 && 103 &&&& 107 && 109 & \\ \hline
&& 113 &&&&&&& \\ \hline
\end{array}

ステップ6: 11以外の11の倍数を消す？

この時点で、次に注目する数は11になります。
これまでと同様に、11を除いて11の倍数を消すことになりますが、その必要があるのでしょうか？
11×素数となる数は、

• 11×2=22
• 11×3=33
• 11×5=55
• 11×7=77

ですが、これまでの手順で既に消えています。
次に消える数は、

• 11×11=121

となりますが、今回の対象である120よりも大きくなります。
ここで、手順は打ち切ります。
ということで、120までの素数は、ステップ5で残った数、となります。

まとめ

120までの素数を並べると、以下の通りです。
\begin{array}{cccccccccc}
2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 \\
31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 \\
73 & 79 & 83 & 89 & 97 &101 & 103 & 107 & 109 & 113 \\
\ \ \ \ & \ \ \ \ & \ \ \ \ & \ \ \ \ & \ \ \ \ &&&&&
\end{array}