1から1000までの間にあるすべての素数を求める問題を考えます。

素数の定義：素数とは1か自分自身でしか割り切れない１より大きい自然数である。

素数の定義から、2、3は素数です。4は2で割り切れるので素数ではありません。ここまでは直ぐに分かりますが、それに続く自然数1つひとつについて素数か否か調べることにします。

偶数は必ず素数2で割り切れますので、素数ではありません。そのため、偶数は調査対象から外します。

調べる対象の数を候補と呼ぶことにします。

3に続く奇数を1つ求めそれを候補とします。候補を3から始まる素数の配列（素数配列と呼ぶ）のすべての要素で割って余りに0になるものがあるならば、この候補は素数ではないので、現在の候補に2を加算して次の候補として調査を繰り返しますが、この候補が1000以上ならば調査は終わりです。

候補を素数配列のすべての要素で割った余りに0になるものがなければ、候補は素数であり、この候補を素数配列に加えます。続いて現在の候補に2を加算して次の候補として上の調査を繰り返します。

調査が終了したとき、2と素数配列のすべての要素が1000までの素数となります。

上記が、1000までの素数を求めるアルゴリズムです。

このアルゴリズムをプログラムで表しますと、次のようになります。

求める素数は2と素数配列primen内の要素番号0からtop-1までの要素の値である。

※※ここで用いたプログラム表現については「ビットから始めるプログラミング」で定義しています。※※