エラトステネスの篩(ふるい)について

素数を求めるアルゴリズム「エラトステネスの篩(ふるい)」について質問があります。

Wikipedia によると
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9% …

【ステップ４】
探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。

と記載されています。
2～1000の間にある素数を調べる場合は、
素数リストの最大値が11のところで累乗が1000 を超えるため
残っている数が素数ということなります。

実際試してみたところ、493 を素数と見なしてしまいました。
493 は 17の倍数なのですが、上記のとおり素数リストの最大値が11のところで
残っている数を素数と考えると、17の倍数の削除が働きません。

ほかの質問でエラトステネスの篩(ふるい)について質問されている方がおられるようですが
もうひとつ理解が足りませんでしたので、申し訳ありませんが
考え方、やり方の間違いなどについて、ご教授をお願いします。

No.1 ベストアンサー 回答者： nebnab 回答日時： 2011/03/19 17:52

＞素数リストの最大値が11のところで累乗が1000 を超えるため

11の平方、つまり11の2乗は121です。
まだ1000を超えていません。
ここが間違っています。

1000をはじめて超える素数の2乗は37の2乗=1369だと思います。

この回答へのお礼

回答ありがとうございます。
とんでもない初歩的なミスでした。。。お恥ずかしい。

ありがとうございました。

お礼日時：2011/03/19 17:59