C++経典のアルゴリズムの問題-選別して質数を求めます

15.Algorithm Gossip:Eratosthenesスクリーニング質量数を求める
説明
自分以外の整数では割り切れない数を素数と呼び,素数を求めるのは簡単であるが,素数をいかに速く求めるかはプログラム設計者や数学者の努力の課題であり,ここでは有名なEratosthenesの素数を求める方法を紹介する.
解法
まず、この問題はループを使用して解くことができることを知っています.指定された数をそれより小さいすべての数で割って、除去できれば質量数ではありませんが、ループの検査回数を減らすにはどうすればいいですか.Nより小さいすべての質量数をどのように求めますか?
まず検査すべき数がNであると仮定すると,実際にはNの開根番号まで検査すればよいという理屈は簡単で,AB=Nと仮定し,AがNより大きい開根番号であれば,事実上Aより小さい前の検査ではBという数を先に検査してNを整除することができる.ただし、プログラムではルート番号を使用すると精度の問題があるため、ii<=Nを使用してチェックでき、実行が速くなります.
さらに、1〜Nを1個のふるいに入れるものとし、例えば、2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 19 21 N
先に2の倍数をふるいにかけます:2 3 5 7 9 11 13 17 19 N
更に3の倍数をふるいにかけます:2 3 5 7 11 17 N
5の倍数をふるい、7の素数をふるい、11の倍数をふるい、最後に残る数が素数になるようにするのがEratosthenesフィルタリング方法(Eratosthenes Sieve Method).
検査の回数をさらに減らすこともできるが,実際には6 n+1と6 n+5を検査すればよい,すなわち2と3の倍数を直接スキップし,プログラム中のifの検査動作を減らすことができる.
コードの例

#include  
#include 
#define N 1000

    int main(void) { int i, j;
        int prime[N+1];

        for(i = 2; i <= N; i++) prime[i] = 1;

        for(i = 2; i*i <= N; i++) { //       
            if(prime[i] == 1) {
                for(j = 2*i; j <= N; j++) { if(j % i == 0)
                    prime[j] = 0;
                }
            }
        }

        for(i = 2; i < N; i++) { if(prime[i] == 1) {
            printf("%4d ", i); if(i % 16 == 0)
                printf("
");
        }
        }

        printf("
"); return 0;
    }