算法學習筆記(17): 素數(shù)篩

素數(shù)篩法枣抱，是一種快速“篩”出2~n之間所有素數(shù)的方法蓝晒。樸素的篩法叫埃氏篩（the Sieve ofEratosthenes氢烘，埃拉托色尼篩）烦却，它的過程是這樣的：

我們把2~n的數(shù)按順序?qū)懗鰜恚?/p>

$\begin{matrix}2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\end{matrix}$

從前往后看执桌，找到第一個未被劃掉的數(shù)鄙皇，2，這說明它是質(zhì)數(shù)鼻吮。然后把2的倍數(shù)（不包括2）劃掉：

$\begin{matrix}\color{blue}{2}&3&\cancel4&5&\cancel6&7&\cancel8&9&\cancel{10}&11&\cancel{12}&13&\cancel{14}&15&\cancel{16}\end{matrix}$

下一個未被劃掉的數(shù)是3育苟，它是質(zhì)數(shù)，把3的倍數(shù)劃掉：

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&5&\cancel6&7&\cancel8&\cancel{9}&\cancel{10}&11&\cancel{12}&13&\cancel{14}&\cancel{15}&\cancel{16}\end{matrix}$

接下來應該是5椎木，但是5已經(jīng)超過 $\sqrt{16}$ 了违柏，所以遍歷結(jié)束博烂，剩下未被劃掉的都是素數(shù)：

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&\color{blue}5&\cancel6&\color{blue}7&\cancel8&\cancel{9}&\cancel{10}&\color{blue}{11}&\cancel{12}&\color{blue}{13}&\cancel{14}&\cancel{15}&\cancel{16}\end{matrix}$

如何？是不是比一個一個判斷快多了漱竖？這個過程寫成代碼就是：

bool isnp[MAXN]; // is not prime: 不是素數(shù)
void init(int n)
{
    for (int i = 2; i * i <= n; i  )
        if (!isnp[i])
            for (int j = i * i; j <= n; j  = i)
                isnp[j] = 1;
}

代碼也很簡潔禽篱。這個算法的復雜度是 $O(n\log\log n)$ ，還是非常優(yōu)秀了馍惹。但是我們可能會發(fā)現(xiàn)躺率，在篩的過程中我們會重復篩到同一個數(shù)，例如12同時被2和3篩到万矾，30同時被2悼吱、3和5篩到。所以我們引入歐拉篩良狈，也叫線性篩后添，可以在 $O(n)$ 時間內(nèi)完成對2~n的篩選。它的核心思想是：讓每一個合數(shù)被其最小質(zhì)因數(shù)篩到薪丁。

我們這次除了把2~n列出來遇西，還維護一個質(zhì)數(shù)表：

$\begin{matrix}2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\end{matrix} \\\text{primes:}\;()$

還是從頭到尾遍歷，第一個數(shù)是2严嗜，未被劃掉粱檀，把它放進質(zhì)數(shù)表：

$\begin{matrix}\color{blue}2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\end{matrix} \\\text{primes:}\;(2,)$

然后我們用2去乘質(zhì)數(shù)表里的每個數(shù)，劃掉它們：

$\begin{matrix}\color{blue}2&3&\cancel4&5&6&7&8&9&10&11&12&13&14&15&16\end{matrix} \\\text{primes:}\;(2,)$

下一個是3漫玄，加入質(zhì)數(shù)表茄蚯，劃掉6、9：

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&5&\cancel6&7&8&\cancel9&10&11&12&13&14&15&16\end{matrix} \\\text{primes:}\;(2,3,)$

下一個是4（注意這里劃掉的數(shù)也要遍歷睦优，只是不加入質(zhì)數(shù)表）第队，先劃掉8，但我們不劃掉12刨秆，因為12 $(12=2\times6=3\times4)$ 應該由它的最小質(zhì)因數(shù)2篩掉，而不是3忆畅。

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&5&\cancel6&7&\cancel8&\cancel9&10&11&12&13&14&15&16\end{matrix} \\\text{primes:}\;(2,3,)$

實際上衡未，對于 $x$ ，我們遍歷到質(zhì)數(shù)表中的 $p$ 家凯，且發(fā)現(xiàn) $p|x$ 時缓醋，就應當停止遍歷質(zhì)數(shù)表终蒂。因為：設 $x=pr(r\ge p)$ （ $p$ 本身是 $x$ 的最小質(zhì)因數(shù)）交洗，那么對于任意 $p'>p$ ，有 $p'x=pp'r=p(p'r)$ 时捌，說明 $p'x$ 的最小質(zhì)因數(shù)不是 $p'$ 掂之，我們不應該在此劃掉它抗俄。

這么說有點抽象脆丁，具體地說，如這里的2能被4整除动雹，則 $4=2\times2$ 槽卫，那么對于任何大于2的質(zhì)數(shù) $p$ ，都有 $4p=2\times2p$ 胰蝠，其中2是一個比 $p$ 更小的質(zhì)數(shù)歼培，所以 $4p$ 應該被2篩掉而不是被 $p$ 篩掉。

下一個是5茸塞，加入質(zhì)數(shù)表躲庄，劃掉10，15：

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&\color{blue}5&\cancel6&7&\cancel8&\cancel9&\cancel{10}&11&12&13&14&\cancel{15}&16\end{matrix} \\\text{primes:}\;(2,3,5,)$

下一個是6钾虐，劃掉12噪窘，6被2整除，跳過禾唁。

……

按這樣的步驟進行下去效览，可以篩掉所有的合數(shù)，并得到一張質(zhì)數(shù)表荡短。

$\begin{matrix}\color{blue}2&\color{blue}3&\cancel4&\color{blue}5&\cancel6&\color{blue}7&\cancel8&\cancel9&\cancel{10}&\color{blue}{11}&\cancel{12}&\color{blue}{13}&\cancel{14}&\cancel{15}&\cancel{16}\end{matrix} \\\text{primes:}\;(2,3,5,7,11,13)$

我們可以保證每個合數(shù)都被篩過丐枉，設任意合數(shù) $x=pr(r\ge p)$ ，其中 $p$ 是 $x$ 的最小質(zhì)因數(shù)掘托，又設 $r=p'r'(r'\ge p')$ 瘦锹， $p'$ 是 $r$ 的最小質(zhì)因數(shù)。在處理 $r$ 時闪盔，要遍歷質(zhì)數(shù)表弯院，直到遇到 $p'$ 時才結(jié)束，所以任意小于等于 $p'$ 的質(zhì)數(shù)與 $r$ 的乘積泪掀，都會在此時被篩掉听绳。

而由于一定有 $p\le p'$ （因為 $x$ 的最小質(zhì)因數(shù)是 $p$ ，而不是 $p'$ ）异赫，所以在處理到 $r$ 時椅挣， $rp$ 一定會被篩到。

代碼如下（C++11風格）：

bool isnp[MAXN];
vector<int> primes; // 質(zhì)數(shù)表
void init(int n)
{
    for (int i = 2; i <= n; i  )
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

注意判斷越界那里最好使用乘法而不是除法塔拳，一般不會溢出鼠证，計算機算除法比乘法要慢得多。

歐拉篩除了解決一些卡埃氏篩的毒瘤題（比如洛谷P3383靠抑，線性篩模板）外量九，在后續(xù)一些數(shù)論算法中還有更多的應用。