06/11/27 20:55:38 3EIwZmwn
>>597
いいかい、n+1が素数かどうかを最も効率よく判定するためには、
n以下の素数が列挙されている必要がある。
これが「エラトステネスのふるい」から得られる知見なのだよ。
そうしてみると、1000個目の素数を探すプログラムには、
・ 次に判定する整数を示すカウンタ
・ 今までに見つかった素数を格納する配列
を確保する必要がある。
1000個目、という指定は、後者の確保する用量が静的に決まるため、
極めて具合が良いのだよ。
「エラトステネスのふるい」と言われて、
教科書どおりの手順しか思いつかない人間には、
残念ながら、創造の才能は無いよ。
与えられた道具は、使い方を工夫して、組み合わせるんだ。