素數驗證算法——直面大數據，素數算法直面

素數驗證算法——直面大數據，素數算法直面

      素數的驗證，可能會被作為所謂“循環練習”的題目。因為其算法實在太簡單（不知道直接暴力循環能不能算一種算法）。經典的方法就是試除，用循環變量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=100000000的數據明顯力不從心。所以，我們可以使用篩選法：依次剔除2、3、5、7等素數的倍數，最後就能得出一張素數表。建表後，查詢素數只要O(1)的時間復雜度。但是對於以上數量級的N，仍然不能很快的求出一張素數表，消耗時間高達2.1s。所以，我們還要加以優化。

      眾所周知，除去2以外，所有的偶數均為合數。所以，素數表內可以除去偶數。即prime[0]代表3是否為素數，prime[1]代表5……而且，篩數也不必篩到N，只要篩到sqrt(N)即可。設key1(i)=i*2+3;key2(i)=(i-3)/2，這分別對應素數表內第i個位置表示的奇數與奇數i在素數表內的存儲位置。原來篩的時候，i*(2,3,4…)簡化為了i*(3,5,7…)。頭一次篩掉的數為key2(key1(i*i))，簡化後為(i*i)*8+3，之後每次累加的數為key2(key1(i+2))-key2(key1(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;
}

      附上各種方法的時間與內存占用統計表（測試環境：MinGw4.9.2，Intel Xeon E3 1230V2，去除IO輸出時間）：