藍影

求質數一直是數學家和程式設計者必經之路。最累人判斷n是不是質數的方式就是從2~(n-1) 一個一個除，只有要任何一個除得盡，就不是質數...

當然沒那麼可憐..

其實有很多相關的經驗法則、定理都已經出來了，只要稍微應用一下，求數字較大的質數並不會花那麼多時間，以下有幾個經驗法則供各位參考

(1) n mod 2 = 0 , then continue ：大家都知道偶數一定不是質數，這個我就不解釋了

(2) 質數只有可能是 6n+1, 6n+5，類似的東西還很多，這二個只是把2、3的倍數抽出來而已

(3) 在檢查時，只要不用檢查 2~(n-1)，而是檢查 2~ sqrt(n)，這個技巧會節省很多時間..

// =====================================================

在此向各位介紹  "埃拉托斯特尼篩法"，步驟如下：

第一步，列出如下這樣以2開頭的序列：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第二步，標出序列中的第一個質數，主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第三步，將剩下序列中，第二項開始每隔一項劃掉(2的倍數,用紅色標出。），主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第四步，如果現在這個序列中最大數小於第一個質數的平方，那麼剩下的序列中所有的數都是質數，否則返回第二步。

本例中，因為25大於2的平方，我們返回第二步：

剩下的序列中第一個質數是3，將主序列中3的倍數劃出（紅色），主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

我們得到的質數有：2，3。

25仍然大於3的平方，所以我們還要返回第二步：

現在序列中第一個質數是5，同樣將序列中5的倍數劃出，主序列成了：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

我們得到的質數有：2 3 5 。

因為25等於5的平方，跳出循環.

結論：去掉紅色的數字，2到25之間的質數是：2 3 5 7 11 13 17 19 23。

(參考網站：wiki)

// =====================================================

這次的程式我寫了三個 function，同時借此比較其效能，
bool IsPrimeBad(unsigned long n); 使用的是傳統的呆呆法
bool IsPrime1(unsigned long n); 則去掉了偶數判斷及 i*i<n (就是上面的法則3) 的功能
void Eratos(unsigned long n); 則使用了 埃拉托斯特尼篩法

為了避免 code 看起來太過凌亂，這次我把主函數 main 拿掉，有興趣要測的人
可以再留言和我說，或者是自己寫一個 main 去測...

// ====================================
// FileName: Prime.cpp
// Author  : Edison.Shih.
// Complier: VC 2008

#include <stdio.h>

#define MAX        (unsigned long)(300000)
unsigned long Table[MAX+1] = {0};

// ====================================
// the bad method
bool IsPrimeBad(unsigned long n)
{
        unsigned i;
        for(i=2; i<n; i++) if(n%i==0) return false;
        return true;
}

// ====================================
// ignore the 2's multiple
bool IsPrime1(unsigned long n)
{
        if(n%2==0 && n!=2) return false;
        unsigned i=0;
        for(i=3; i*i<=n; i+=2) if(n%i==0) return false;
        return true;
}

// ====================================
// Eratosthenes method
void Eratos(unsigned long n){
        unsigned long i, j;
        for(i=2; i<=n; i++){
                if(IsPrime1(i)) {
                        j = 2;
                        while(j*i<=n) Table[j*i] = 1, j++;
                }
                if(i*i>n) return;
        }
}

// ====================================

程式出來的結果其實讓我有點意外，

我測了三十萬筆資料，
測三次取平均值下來的結果..

傳流的呆呆法花了 75.708 秒
而我所提供的方法(第二種) 花了 1.933 秒
另外 Eratosthenes 花了 1.982 秒，
而且 Eratosthenes 每次花的時間都比第二種方法還慢..

看來 Eratosthenes 還是純觀賞就好...