>>597
いいかい、n+1が素数かどうかを最も効率よく判定するためには、
n以下の素数が列挙されている必要がある。
これが「エラトステネスのふるい」から得られる知見なのだよ。

そうしてみると、1000個目の素数を探すプログラムには、
　・　次に判定する整数を示すカウンタ
　・　今までに見つかった素数を格納する配列
を確保する必要がある。
1000個目、という指定は、後者の確保する用量が静的に決まるため、
極めて具合が良いのだよ。

「エラトステネスのふるい」と言われて、
教科書どおりの手順しか思いつかない人間には、
残念ながら、創造の才能は無いよ。
与えられた道具は、使い方を工夫して、組み合わせるんだ。