這個(gè)線性復(fù)雜度的歐拉素?cái)?shù)篩法，愛(ài)了愛(ài)了

今天講一下關(guān)于歐拉篩法的原理和代碼實(shí)現(xiàn)，實(shí)不相瞞，我也才剛get到這個(gè)篩法的點(diǎn)，乘著記憶清晰來(lái)教一遍梳理一下思路。

我查閱資料的時(shí)候也在很多博客和公眾號(hào)上看到關(guān)于歐拉篩法的解釋和代碼實(shí)現(xiàn)，然后想學(xué)習(xí)了之后用我自己的話重新描述一遍，希望我的角度能讓你有所收獲！

歐拉篩法與埃氏篩法一樣，都是圍繞【素?cái)?shù)的倍數(shù)不是素?cái)?shù)】這個(gè)核心原理來(lái)展開(kāi)的，有關(guān)埃氏篩法請(qǐng)移步我的上一篇博客“埃氏篩法的詳解”，但是它比埃氏篩法更高效，當(dāng)數(shù)據(jù)量足夠大的時(shí)候，歐拉篩法的時(shí)間是埃氏篩法時(shí)間的十分之一甚至更少。

現(xiàn)在我們正式展開(kāi)歐拉篩法的學(xué)習(xí)。

歐拉篩法效率高的一個(gè)重要原因是，它不會(huì)重復(fù)標(biāo)記一個(gè)數(shù)是不是素?cái)?shù)的倍數(shù)，例如：6是素?cái)?shù)2的倍數(shù)，同時(shí)也是素?cái)?shù)3的倍數(shù)，歐拉算法能做到只標(biāo)記一次6。

我們先看一下代碼

#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
    int n, cnt = 0; // n是你要找的素?cái)?shù)范圍，cnt代表在這個(gè)范圍內(nèi)素?cái)?shù)的個(gè)數(shù)

    int prime[100001];// 用來(lái)保存素?cái)?shù)，注意，是用數(shù)組的值而不是用下標(biāo)保存哦！

    bool visited[100001];// 就是這個(gè)數(shù)組！用來(lái)記錄一個(gè)數(shù)是否是某個(gè)素?cái)?shù)的倍數(shù)，標(biāo)記它
    
    scanf("%d", &n); // 輸入你想查找的范圍

    memset(visited, false, sizeof(visited));// 初始化 

    memset(prime, 0, sizeof(prime));// 初始化
    
    for(int i = 2; i <= n; i++)

    {

        if(!visited[i])// 如果沒(méi)有被標(biāo)記過(guò)

        {
            prime[cnt++] = i;// 那么它就是素?cái)?shù)啦~，存起來(lái)存起來(lái)，cnt記得+1 
        }

        for(int j = 0; j<cnt && i*prime[j]<=n; j++) // 這個(gè)循環(huán)是最難理解的部分，我將在下文詳細(xì)解釋

        {

            visited[i*prime[j]] = true;// 標(biāo)記素?cái)?shù)倍數(shù)

            if(i % prime[j] == 0) break;// 這一步跳出循環(huán)是歐拉篩法高效率的關(guān)鍵，也是同一個(gè)合數(shù)只被標(biāo)記一次的關(guān)鍵

        }

    }
    return 0;
}

ok，代碼如上，可以直接拷貝過(guò)去試試哦！

現(xiàn)在來(lái)詳細(xì)分解一下那個(gè)for循環(huán)代碼

此處我們暫時(shí)拋開(kāi) if(i % prime[j] == 0) break; 這句代碼來(lái)討論

for循環(huán)的循環(huán)變量 j 每次都從 0 開(kāi)始跑，而這個(gè) j 是從 prime[] 數(shù)組中取數(shù)據(jù)的，我們就可以這樣等價(jià)，for循環(huán)每次都從已經(jīng)找到的素?cái)?shù)中從頭開(kāi)始取值。
例如 prime[] 中已經(jīng)判斷出了 2,3,5,7 那么for循環(huán)第一次取值2，如果沒(méi)有跳出的話，第二次取值3，然后沒(méi)有跳出的話就一直循環(huán)到已經(jīng)找出的素?cái)?shù)末尾。

然后

visited[i*prime[j]] = true;

這個(gè)代碼段，是用來(lái)標(biāo)記素?cái)?shù)倍數(shù)的，例如，當(dāng) i 等于2的時(shí)候，素?cái)?shù)數(shù)組里只存在一個(gè)素?cái)?shù) 2 ，然后進(jìn)入 for 循環(huán)，for 循環(huán)會(huì)將 2 取出來(lái)與 i 相乘，得到 2 的倍數(shù) 4 ，標(biāo)記它，然后結(jié)束 for 循環(huán)。跑過(guò) i = 3，執(zhí)行到 i = 4 的時(shí)候，千萬(wàn)不要以為這個(gè)時(shí)候 for 循環(huán)不執(zhí)行了！ 這個(gè)時(shí)候 for 循環(huán)依舊會(huì)盡職地把 2 取出來(lái)和 4 相乘，將 2 的倍數(shù) 8 標(biāo)記！然后 不會(huì)取到第二個(gè)素?cái)?shù) 3 ，因?yàn)?4 % 2 == 0 -------

縱觀之，如果我們不把

if(i % prime[j] == 0) break;

這段代碼放在內(nèi)的話， for 循環(huán)的作用就是將素?cái)?shù)的倍數(shù)都標(biāo)記上。

討論關(guān)鍵性代碼段 if(i % prime[j] == 0) break;

然后我們開(kāi)始討論上面那一小段代碼的關(guān)鍵性作用：

18 是素?cái)?shù) 3 的倍數(shù)，但是我們并不會(huì)用 3 的倍數(shù)來(lái)標(biāo)記掉 18 , 因?yàn)榧偃缥覀冇?3 來(lái)標(biāo)記 18 ，那么 i 勢(shì)必要跑到 6 這樣 i * 3 才會(huì)標(biāo)記掉18， 但是在這之前 i 就已經(jīng)被 3 之前的一個(gè)素?cái)?shù) 2 弄死了，退出循環(huán)了。
那么為什么要這么做？因?yàn)?6 既然能被 2 整除， 那么 18 遲早會(huì)被 2 標(biāo)記，所以這里就不要再用 3 來(lái)重復(fù)標(biāo)記 18。
你問(wèn)我怎么知道 18 遲早會(huì)被 2 標(biāo)記的？ 6 能被 2 整除，那么 3 乘 6 就可以分解為 3 乘 2 乘 3， 也就是 2 乘 9 ， 2 乘 9 就標(biāo)記掉了18.

如果你看懂了上面的代碼，我們?cè)賮?lái)總結(jié)一下

有個(gè)規(guī)律，不知道大家發(fā)現(xiàn)沒(méi)有，凡是 i 跑到偶數(shù)位的時(shí)候，它永遠(yuǎn)只能與素?cái)?shù) 2 相乘一次來(lái)標(biāo)記掉一個(gè)數(shù)，然后因?yàn)槟苷?2 而退出循環(huán)。 從這個(gè)規(guī)律，這個(gè)篩法的時(shí)間復(fù)雜度就可見(jiàn)一斑了。
外層 i 循環(huán)用來(lái)選出素?cái)?shù)和作為標(biāo)記素?cái)?shù)倍數(shù)的倍數(shù)因子，內(nèi)層 j 循環(huán)用來(lái)從素?cái)?shù)中最小的開(kāi)始遍歷作為標(biāo)記素?cái)?shù)倍數(shù)的素?cái)?shù)因子。然后通過(guò) i % 素?cái)?shù) == 0 來(lái)退出標(biāo)記避免重復(fù)標(biāo)記。

謝謝你的觀看！
也可以轉(zhuǎn)到我的個(gè)人博客上去觀看。
http://hsluoyang.club/