素数筛算法浅谈

简介

素数筛是一种快速筛选出2~n（设给定的上界为n）的算法，在许多的数论算法中都有较为广泛的应用

算法

埃氏筛

简介

埃氏筛是一种朴素的筛素数的算法，由希腊数学家埃拉托斯特尼所提出，因而得名。它的算法思想是这样的：要得到自然数n以内的全部素数，必须把不大于$\sqrt{n}$的所有素数的倍数剔除，剩下的就是素数。

思路

它实现的思路也相对简单

以n = 20为例，对于序列

$$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$

从前往后遍历，第一个数是2，将其列为素数，并删去序列中2的所有倍数，余下的数组成新的序列

$$2,3,5,7,9,11,13,15,17,19$$

而后遍历至3，将其列为素数，并删去序列中3的所有倍数……重复该过程直至$\lfloor \sqrt{n}\rfloor$

代码实现

代码实现也非常简单

// 这里给到的是最优化的埃氏筛，就不列出退化的算法了
void getprime(int n, int notprime[])
{
    int i, j;
    for (i = 2; i * i <= n; ++i)
        if (!notprime[i])
            for (j = i * i; j <= n; j += i)
                notprime[j] = 1;
    return;
}

复杂度及其优劣

埃氏筛的复杂度为$O(n\log \log n)$，由如下公式计算得出

$$M=\underset{n\to \mathrm{\infty }}{lim}(\sum _{p\le n}\frac{1}{p}-\ln (\ln (n)))$$

其中$M$为Meissel–Mertens常数，$p$为质数

但是，埃氏筛仍然会有不少无谓的损耗，比如，12既会被2筛一次，又会被3筛一次，因而在数据量较大时仍有超时风险，容易被毒瘤数据卡，另外一种筛法欧拉筛就可以减少这样的损耗，因而更快。

欧拉筛（线性筛）

简介

欧拉筛，又叫线性筛，这个别名正是因为它能在$O(n)$的线性时间内筛出2~n的所有素数，较埃氏筛更优

思路

我们在筛选的同时，维护一个素数序列，将所有筛得的素数都加入到该序列中

仍以n = 20为例，对于序列

$$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$
$$primes:()$$

从前往后遍历，第一个数是2，将其加入到素数序列中

$$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$
$$primes:(2)$$

然后用当前遍历的数2去乘更新后的素数序列中的每一个素数，并将所得的结果2*2=4标记为非素数

接下来是3，因为并未被标记为非素数，将其加入到素数序列中

$$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$
$$primes:(2,3)$$

用当前遍历的数3去乘更新后的素数序列中的每一个素数，将所得结果3*2=6、3*3=9标记为非素数

下一个数是合数4，已经被标记为非素数，因而直接用4去乘素数序列中的素数，关键来了：

我们知道，$12=2\ast 6=3\ast 4$，那么12是不是会4和6被筛两次呢？复杂度是不是又退化了？

并不是的，当我们遍历到某个合数时，仍然用它去乘素数序列中的素数，但为了防止上述如12那样的情况出现，我们增加一个限制条件

对于合数$x$，在遍历至素数序列中的素数$p$时，若发现$p|x$，则结束对$x$的处理，继续遍历下一个数

上述的语句等效于素数$p$是合数$x$的最小质因数，也就是说有等式$x=k\ast p$，而对于$x$的任意倍数，均有$p$为其最小质因数，因而我们通过上述处理保证了每一个合数仅被其最小质因数筛去，从而避免了无端的损耗。

代码实现

非常简单，只需要将思路所用的自然语言翻译即可

void getprime(int n, int notprime[], int prime[], int cnt)
{
    int i, j;
    for (i = 2; i <= n; ++i)
    {
        if (!notprime[i]) prime[cnt++] = i;
        for (j = 0; j < cnt && i * prime[j] <= n; ++j)
        {
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return;
}

总结

素数筛的泛用性自不必多说，本文简述了两种素数筛算法，希望能帮助阅读本文的诸君加深对其的了解和对算法发自内心的热爱，谨以此文献给真正热爱Coding的人，望共勉。

P.S. 笔者如有陈述不周之处还望斧正