ふるい

説明

エラトステネスの篩アルゴリズムを実装して、与えられた数値以下の素数をすべて見つけるプログラムを作りましょう。

素数とは、1より大きい数で、1とその数自身でしか割り切れない数のことです。 たとえば、2、3、5、7、11、13は素数です。 一方、6は素数では_ありません_。6は1とその数自身だけでなく、2と3でも割り切れるからです。

エラトステネスの篩を使うには、まず2から与えられた数値までのすべての数値を並べた配列を作ります。 そして、次の手順を繰り返します。

1. 配列の中で、まだ印が付いていない次の数値を見つけます（印が付いている数値は飛ばします）。 これが素数です。
2. その素数の倍数すべてに、素数ではないと印を付けます。

配列のすべての数値を見終えるまで、この手順を繰り返します。 最後に、印が付いていない数値がすべて素数です。

例

10以下の素数を求める場合を考えてみましょう。

• 2、3、4、5、6、7、8、9、10を書き出し、どれにも印を付けずにおきます。
• 2には印が付いていないので、素数です。 4、6、8、10に「素数でない」と印を付けます。
• 3には印が付いていないので、素数です。 6と9に素数でないと印を付けます_（6への印付けは任意です。すでに印が付いているため）_。
• 4には「素数でない」と印が付いているので、飛ばします。
• 5には印が付いていないので、素数です。 10に素数でないと印を付けます_（任意です。すでに印が付いているため）_。
• 6には「素数でない」と印が付いているので、飛ばします。
• 7には印が付いていないので、素数です。
• 8には「素数でない」と印が付いているので、飛ばします。
• 9には「素数でない」と印が付いているので、飛ばします。
• 10には「素数でない」と印が付いているので、確認する数値がもうないため、ここで終了します。

すべての数値を調べ終えると、2、3、5、7にはまだ印が付いていないことがわかります。つまり、これらが10以下の素数です。

---

出典

Wikipediaのエラトステネスのふるい