はじめに
ガレージセールで、コンピューター部品がランダムに入った大きな箱を買いました。その部品を組み立てて、自作のコンピューターを作り始めています。
部品の組み合わせを変えて性能を試してみたくなり、それぞれのコンピューターを比べるためのベンチマークプログラムを自分で作ることにしました。そこで選んだのが、有名な"Sieve of Eratosthenes"というアルゴリズムです。古くからあるアルゴリズムですが、コンピューターを限界まで追い込んでくれるはずです。
説明
この演習の課題は、エラトステネスの篩アルゴリズムを実装して、与えられた数値以下の素数をすべて求めるプログラムを作成することです。
素数とは、1より大きい数値のうち、1とその数自身でのみ割り切れる数のことです。
たとえば、2、3、5、7、11、13は素数です。
一方、6は素数では_ありません_。1とその数自身だけでなく、2や3でも割り切れるからです。
エラトステネスの篩を使うには、まず、2から与えられた数値までの数値をすべて書き出します。
次に、以下の手順を行います。
- 印が付いていない次の数値を見つけます（印が付いた数値は飛ばします）。
これが素数です。
- その素数の倍数にすべて、素数ではないと印を付けます。
すべての数値を見終わるまで、この手順を繰り返します。
最後まで残った、印の付いていない数値がすべて素数です。
エラトステネスの篩では、各数値が割り切れるかどうかを1つずつ調べるのではなく、足し算（素数を繰り返し足す）や掛け算（倍数を直接計算する）を使って、それぞれの素数の倍数に印を付けていきます。
テストは、このアルゴリズムを実装したかどうかまでは確認しません。正しい素数を求められたかどうかだけを確認します。
例
10以下の素数を求める場合を考えてみましょう。
-
2、3、4、5、6、7、8、9、10を書き出し、どれにも印を付けないでおきます。
2 3 4 5 6 7 8 9 10
-
2には印が付いていないので、素数です。
4、6、8、10に「素数ではない」と印を付けます。
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3には印が付いていないので、素数です。
6と9に素数ではないと印を付けます_（6はすでに印が付いているので、付けても付けなくてもかまいません）_。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4には「素数ではない」と印が付いているので、飛ばします。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5には印が付いていないので、素数です。
10に素数ではないと印を付けます_（すでに印が付いているので、付けなくてもかまいません）_。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6には「素数ではない」と印が付いているので、飛ばします。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7には印が付いていないので、素数です。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8には「素数ではない」と印が付いているので、飛ばします。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9には「素数ではない」と印が付いているので、飛ばします。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10には「素数ではない」と印が付いているので、確認する数値がもう残っていないため、ここで終了します。
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
すべての数値を確認した結果、2、3、5、7にはまだ印が付いていないことがわかります。つまり、これらが10以下の素数です。
