素数筛

· 2021-11-2   · 次阅读   · 字数统计: 968字   · 阅读时长≈ 3分钟

  · 算法   · 数论

素数筛法，是一种快速“筛”出2~n之间所有素数的方法，下面将介绍两种线性筛

埃拉托斯特尼筛

埃拉托斯特尼筛，也叫埃氏筛（The Sieve of _Eratosthenes_）
它的筛数过程如下：

我们把2~n的数按顺序写出来：

公式

从前往后看，找到第一个未被划掉的数，2，这说明它是质数。然后把2的倍数（不包括2）划掉：

公式

下一个未被划掉的数是3，它是质数，把3的倍数划掉：

公式

接下来应该是5，但是5已经超过 [公式] 了，所以遍历结束，剩下未被划掉的都是素数：

如何？是不是比一个一个判断快多了？这个过程写成代码就是：

bool isnp[MAXN]; // is not prime: 不是素数
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) ，还是非常优秀了。但是我们可能会发现，在筛的过程中我们会重复筛到同一个数，例如12同时被2和3筛到，30同时被2、3和5筛到
所以我们引入欧拉筛，也叫线性筛，可以在 O(n) 时间内完成对2~n的筛选。它的核心思想是：让每一个合数被其最小质因数筛到

欧拉筛

我们这次除了把2~n列出来，还维护一个质数表：

公式

还是从头到尾遍历，第一个数是2，未被划掉，把它放进质数表：

公式

然后我们用2去乘质数表里的每个数，划掉它们：

公式

下一个是3，加入质数表，划掉6、9：

公式

下一个是4（注意这里划掉的数也要遍历，只是不加入质数表），先划掉8，但我们不划掉12，因为12 [公式] 应该由它的最小质因数2筛掉，而不是3

公式

实际上，对于 [公式] ，我们遍历到质数表中的 [公式] ，且发现 [公式] 时，就应当停止遍历质数表。因为：设 [公式] （ [公式] 本身是 [公式] 的最小质因数），那么对于任意 [公式] ，有 [公式] ，说明 [公式] 的最小质因数不是 [公式] ，我们不应该在此划掉它

这么说有点抽象，具体地说，如这里的2能整除4，则 [公式] ，那么对于任何大于2的质数 [公式] ，都有 [公式] ，其中2是一个比 [公式] 更小的质数，所以 [公式] 应该被2筛掉而不是被 [公式] 筛掉

我们再来看 8，因为 8 能被 2 整除，如果继续进行之后的判断，就会有 $8 * 3 = 2 * 6$ 这样的情况发生，即还会被 2 进行一次筛选，所以 $8 * 3 = 2 * 6 = 12$ 应该被 2 筛除而不是这里的 3

下一个是5，加入质数表，划掉10，15：

公式

下一个是6，划掉12，6被2整除，跳过

……

按这样的步骤进行下去，可以筛掉所有的合数，并得到一张质数表

公式

我们可以保证每个合数都被筛过，设任意合数 [公式] ，其中 [公式] 是 [公式] 的最小质因数，又设 [公式] ， [公式] 是 [公式] 的最小质因数。在处理 [公式] 时，要遍历质数表，直到遇到 [公式] 时才结束，所以任意小于等于 [公式] 的质数与 [公式] 的乘积，都会在此时被筛掉

而由于一定有 [公式] （因为 [公式] 的最小质因数是 [公式] ，而不是 [公式] ），所以在处理到 [公式] 时， [公式] 一定会被筛到

代码如下：

bool isnp[MAXN];
vector<int> primes; // 质数表
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;
        }
    }
}

注意判断越界那里最好使用乘法而不是除法，一般不会溢出，计算机算除法比乘法要慢得多

原文链接：算法学习笔记(17): 素数筛