埃氏篩法

一個判斷素數(shù)的高效算法

關(guān)于埃氏篩法的百度百科解釋在這里埃拉托斯特尼篩法，當(dāng)然我不可能給個百度百科的解釋就撤，那會被打死的。
眾所周知，素數(shù)指的是除了1和它本身之外沒有其它約數(shù)的數(shù)
我們假定一個數(shù)num，那么如果我們想通過編程來判斷它是不是素數(shù)，我們首先通過它的定義想到暴力枚舉方法，即用for循環(huán)配合取模操作實現(xiàn)，c++代碼如下

bool flag = true; // flag作為標(biāo)志來標(biāo)識這個數(shù)是不是素數(shù)，默認(rèn)設(shè)置為true
for(int i=2;i<num/2;i++)
{
    if(num % i == 0)
    {
        flag = false; // 如果能被整除了，那就不是素數(shù)，退出循環(huán)
        break;
    }
}
if(flag)
{
    cout<<"數(shù)："<<num<<"是素數(shù)"<<endl;
}

當(dāng)然這種方法就顯得很麻煩，雖然直觀易懂，但是時間復(fù)雜度達到了n^2級。
當(dāng)然如果稍微改進一點的話就會知道把我上面的代碼循環(huán)中的i < num/2改成i*i < num，時間可以縮短。但是仍不夠明顯。

快樂的分割線

下面我們開始埃氏篩法的學(xué)習(xí)

看過上圖百度百科的同學(xué)應(yīng)該明白，埃氏篩法是范圍判斷素數(shù)的方法，即，你給出一個數(shù)n，我用埃氏篩法能判斷從1-n的所有素數(shù)出來。

原理

素數(shù)的倍數(shù)肯定不是素數(shù)

給定一個數(shù)n，我們開一個大小為n+1的bool型數(shù)組，即 bool nums[n+1] ，并全部初始化為false， 在這里聲明一點，這個數(shù)組的 nums[0] 與 nums[1] 我們并不會使用到。
建立了這樣一個數(shù)組之后，我們就可以直接開干啦，我們首先要找到最小的素數(shù)，即2，從而開始循環(huán)開炮
OK非常棒，現(xiàn)在我們已經(jīng)能找出素數(shù)中的最小者了，任務(wù)完成一半！
接下來，我們應(yīng)用我們的原理——素數(shù)的倍數(shù)肯定不是素數(shù)
這里有張表

加入我們要求10以內(nèi)的素數(shù)，開一個nums[11]，然后定位找到最小的素數(shù)->2，以2為基點，開炮，把2的倍數(shù)全部打死，當(dāng)然這個也是有范圍的，2的倍數(shù)我們只要判斷到小于n就可以了，即小于10。然后2的倍數(shù)打死完了，再找幸存的最小素數(shù)3，以3為基點，開炮，在3的炮火攻擊下，上次僥幸存活的9被揪出來打死了。***我們會一直判斷，直到我們的基點達到一個臨界點——小于等于n的開根號，這樣我們就把所有潛藏的合數(shù)敵人全部消滅了，不信你瞅瞅？ ***

原理如此，接下來附上這一部分的代碼，看完代碼之后我會有一個小小的問題遺留給大家思考

int main() // 這里只給出實現(xiàn)代碼了，上面的頭文件什么的都沒寫了
{
    int num;
    cin >> num;
    bool* nums = new bool[num];   // 這里我們?nèi)绻枰米兞縿?chuàng)建數(shù)組的話必須這樣創(chuàng)建喔！
    for (int i = 0; i < num; i++)
    {
        nums[i] = true;
    }
    int sn = sqrt(num);
    for (int i = 2; i <= sn; i++) /* 從最小的素數(shù)2開始開炮*/
    {
        if (nums[i])
        {
            for (int j = i * i; j < num; j+=i)  // 此處需要注意，我們開炮的時候，第一顆炮彈直接打到i的平方上，這是避免了重復(fù)判斷，j每次要增長i
            {
                nums[j] = false;   // 跟我一起，開炮?。?            }
        }
    }
    for (int i = 2; i < num; i++)
    {
        if (nums[i])
        {
            cout << i << "\t";  // 打印出選出來的素數(shù)你看看，這里我喜歡用制表符，個人習(xí)慣，看著舒服
        }
    }

    delete []nums;  // 最后可別忘了釋放指針內(nèi)存哦，并且將指針置空，養(yǎng)成好習(xí)慣，不要野指針！
    nums = nullptr;
    return 0;
}

好了，代碼部分結(jié)束，最后我還遺留一個問題，你們有沒有發(fā)現(xiàn)，我們這里重復(fù)判斷了？比如我已經(jīng)判斷12是偶數(shù)了，已經(jīng)殺死了，但是我以3為基點開炮的時候，還是會再打它一次，炸尸，這會不會浪費我們的炮彈資源（時間）呢？該如何改進這個問題呢？思考一下？

謝謝你來看我！