素数検証アルゴリズム-ビッグデータに直面

素数の検証は、いわゆる「サイクル練習」のテーマにされる可能性があります.そのアルゴリズムはあまりにも簡単だからだ(直接暴力サイクルがアルゴリズムと言えるかどうか分からない).古典的な方法は試除であり,サイクル変数iで2からn−1まで,型取りが0のものがあれば直接return falseとする.最後に、まだ0が出ていないので、return trueです.このアルゴリズムはn−1をsqrt(n)として最適化することもできる.原理は、xをsqrt(n)より大きい数とし、n=xyとするとyは必ずsqrt(n)より小さいので、sqrt(n)を検証すればyを検証することができ、xを検証したことに相当する.
このような暴力アルゴリズムは,N個の数が検証されると,時間的複雑度がO(sqrt(N)*N)となり,N=1億円のようなデータに対して明らかに力不足である.したがって,フィルタリング法を用いて,2,3,5,7などの素数の倍数を順次除去し,最後に素数表を1枚得ることができる.テーブル作成後,クエリ素数はO(1)の時間的複雑度のみである.しかし,以上の桁のNについては,素数表をすぐに求めることができず,2.1 sの消費時間を費やした.だから、私たちは最適化しなければなりません.
2を除いたすべての偶数は合数であることが知られている.したがって、素数テーブル内では偶数を除去することができる.すなわちprime[0]は3が素数であるか否かを表し、prime[1]は5を表す・・・また、ふるい数もNにふるう必要はなく、sqrt(N)にふるい合わせればよい.key 1(i)=i*2+3とする.key 2(i)=(i−3)/2は、素数テーブル内のi番目の位置で表される奇数と奇数iの素数テーブル内の記憶位置にそれぞれ対応する.ふるいにかけると、i*(2,3,4...)はi*(3,5,7...)に簡略化されます.最初にふるい落とした数はkey 2(key 1(i*i)*8+3,その後の累積数はkey 2(key 1(i+2)−key 2(key 1(i)),簡略化後i*2+3となり,導出が完了するとプログラムが書きやすくなる.ソースコードを次に示します.

#include <cstring>

#include <cmath>

#include <cstdio>

using namespace std;



const int N=100000001;

const int N1=(N-3)/2;

bool prime[N1+1];

int tmp;



int main(void){

    memset(prime,true,sizeof(prime));

    for (int i=0;i<(int(sqrt(N))-3)>>1;++i){

        if (prime[i]){

            tmp=((i*i)<<3)+3;

            while (tmp<N1){

                prime[tmp]=false;

                tmp+=(i<<1)+3;

            }

        }

    }

    printf("%d\t",2);

    for (int i=0;i<N1;++i)

        if (prime[i])   printf("%d\t",i*2+3);

    return 0;

}

各種方法の時間とメモリ占有統計表(試験環境:MinGw 4.9.2、Intel Xeon E 3 1230 V 2、IO出力時間を除く)を添付する.
 
時間
メモリ
暴力試験除法
N/A(長すぎます)
1Mb
地味ふるい分け
2.1s
98Mb
さいてきフィルタほう
1.0s
50Mb