エラトステネスの篩（ふるい） The sieve of Eratosthenes

素数の項目で紹介した素数判定プログラムは、与えられた１つの数 x が素数であるか否かを判定するだけでしたが、多くの問題を解く場合、あらかじめ作成された素数表を用いるのが効率的です。

与えられた範囲内の全ての素数を列挙するための高速なアルゴリズムが、エラトステネスの篩（ふるい） The sieve of Eratosthenes です。エラトステネスの篩は、以下の手順で素数表を生成します。ここで、素数表を prime[x] が真ならば x は素数、偽ならば x は合成数（素数ではない整数）であるようなブール型の１次元配列とします。

	2 以上の整数を列挙しておく
	最小である 2 を残して、その倍数をすべて消す
	残った最小の 3 を残して、その倍数をすべて消す
	残った最小の 5 を残して、その倍数をすべて消す
	以下同様に、まだ消えていない最小の数を残してその倍数を消すことを繰り返せば、素数だけが残る

エラトステネスの篩を実装したプログラム例を以下に示します。

001 void eratos ( int n, bool prime[]){
002     for ( int i = 0; i <= n; i++ ) prime[i] = false;
003     // 奇数を素数の候補とする
004     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
005     prime[2] = true;
006     int limit = (int)sqrt((double)n) + 1;
007     // 合成数でない奇数だけを残す
008     for ( int i = 3; i <= limit; i += 2 ){
009         if ( !prime[i] ) continue;
010         // i は素数　i の倍数をすべて消す
011         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
012     }
013 }

このプログラムは、以下のように多少改良することができます。

void eratos ( int n, bool prime[]){
    for ( int i = 0; i <= n; i++ ) prime[i] = false;
    // 奇数を素数の候補とする
    for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
    prime[2] = true;
    int limit = (int)sqrt((double)n) + 1;
    // 合成数でない奇数だけを残す
    for ( int i = 3; i <= limit; i += 2 ){
        if ( !prime[i] ) continue;
        for ( int j = i * i, k = i * 2; j <= n; j += k )
        prime[j] = false;
    }
}