什么是素?cái)?shù)篩？

素?cái)?shù)篩是一種求所有小于n的所有素?cái)?shù)的方法，把從2開(kāi)始的所有合數(shù)逐步篩掉留下素?cái)?shù)。

埃氏篩

埃氏篩的思路非常簡(jiǎn)單，從2開(kāi)始篩去2的所有倍數(shù)，接著從剩下的最小數(shù)字3開(kāi)始，篩去3的所有倍數(shù)，依次下去，每一次都篩去上一次剩下的數(shù)中最小的數(shù)k的所有倍數(shù)，最后剩下的數(shù)就是2～n中所有的素?cái)?shù)。

那為什么剩下的數(shù)中最小的就一定是素?cái)?shù)呢？因?yàn)橐粋€(gè)數(shù)的因子一定是不超過(guò)其本身的，而小于這個(gè)數(shù)的所有倍數(shù)均已經(jīng)被篩去了，所以剩下的數(shù)中最小的就一定是素?cái)?shù)。

埃氏篩實(shí)現(xiàn)

bool vis[MAXN]; //用于標(biāo)記下標(biāo)i是否是素?cái)?shù)
int prime[MAXN], x; //prime用于存放素?cái)?shù)，x是prime數(shù)組的下標(biāo)指針
void PrimeFilter(int n){ //埃氏篩 時(shí)間復(fù)雜度：O(nloglogn)
    vis[0] = vis[1] = true;
    for(int i = 2; i <= n; i++){
        if(!vis[i])prime[x++] = i;
        for(int j = 2; j * i <= n; j++)vis[i*j] = true; //將這個(gè)素?cái)?shù)的所有倍數(shù)篩掉
    }
}

歐拉篩

在埃氏篩的步驟中我們可以發(fā)現(xiàn)，一個(gè)合數(shù)可能被多次篩去，比如6，即是2的倍數(shù)，也是3的倍數(shù)，被篩去了兩次，這樣浪費(fèi)了很多時(shí)間。歐拉篩的基本思想就是讓每個(gè)合數(shù)只被它的最小質(zhì)因數(shù)篩去一次，避免重復(fù)。

歐拉篩實(shí)現(xiàn)

void EulaFilter(int n){ //歐拉篩
    vis[0] = vis[1] = true;
    for(int i = 2; i<=n; i++){
        if(!vis[i])prime[x++] = i;
        for(int j = 0; j < x; j++){
            if(i * prime[j] > n)break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0)break;
        }
    }
}