008: 「夜の金網をくぐり抜け」のヒント¶

難易度: ☆

ヒント1

0から n までの各整数について、素数候補かどうかを表すリストを作ります。 0と1は素数ではありません。

ヒント2

ある数 p がまだ素数候補として残っているなら、p の倍数は素数ではありません。ただし、p 自身は消しません。

ヒント3

p の倍数を消すときは、p * 2 ではなく p * p から始められます。 p * 2、p * 3 のような小さい倍数は、もっと小さい素数の段階ですでに消えています。

ヒント4

調べる p は、p * p <= n の間だけで十分です。最後に、素数候補として残っている番号をリストにします。