埃氏篩法

一個判斷素數(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ù)雜度達(dá)到了n^2級贴妻。
當(dāng)然如果稍微改進(jìn)一點的話就會知道把我上面的代碼循環(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被揪出來打死了寥掐。***我們會一直判斷靴寂，直到我們的基點達(dá)到一個臨界點——小于等于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為基點開炮的時候图张，還是會再打它一次锋拖，炸尸，這會不會浪費我們的炮彈資源（時間）呢祸轮？該如何改進(jìn)這個問題呢兽埃？思考一下？

謝謝你來看我适袜！