线性筛小记

发布于 2022-09-22  538 次阅读

之前线性筛写的有点乱，重新整理一下，又看不懂的地方又改了改

前言

筛法是数论中的一个重要的思想,这篇文章介绍埃氏筛和它的优化欧拉筛.

思想

首先我们需要知道什么是素数和合数

我上高一才刚分清

  • 合数: 可以被$1$和它自己及其他数整除的.
  • 素数(质数): 只能被它自己和$1$整除的.

对于一个数(除了$1$,$0$),他大于$1$的整数倍一定是一个合数.

这个命题显然成立.

例如$2$

他大于$1$的整数倍$4$,$6$,$8$,$10$等,这些数都是合数.

我们的算法就是把非$0$和$1$的数字乘上多倍后,打上标记,标记这些是合数,最后没有标记的就是素数了.

核心代码

void sieve ()
{
    composite[0] = true;  //0和1都是合数
    composite[1] = true;
    for (register int i = 2; i <= n; i++)  //一直筛到n
        for (register int j = i + i; j <= n; j += i)  //如果一个数是合数,那么它的倍数也一定是合数
            composite[j] = true;  //标记合数
}

食用方法（以洛谷P3383 【模板】线性筛素数）为例

#include <algorithm>
#include <cstdio>
#include <iostream>
#define maxn 10000005
using namespace std;

bool composite[maxn] = {};
int num = 0, n, m;

void sieve ()
{
    composite[0] = true;  //0和1都是合数
    composite[1] = true;
    for (register int i = 2; i <= n; i++)  //一直筛到n
        for (register int j = i + i; j <= n; j += i)  //如果一个数是合数,那么它的倍数也一定是合数
            composite[j] = true;  //标记合数
}

int main ()
{
    ios::sync_with_stdio (false); //关同步
    cin.tie (0);
    cout.tie (0);

    cin >> n >> m;

    sieve ();  //筛一遍

    int k;
    while (m--)
    {
        cin >> k;
        if (composite[k])
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    return 0;
}

欧拉筛二三事

其实没什么辣，欧拉筛只是埃筛的一个小优化。

我们分析一下埃筛的代码：

void sieve ()
{
    composite[0] = true;  //0和1都是素数
    composite[1] = true;
    for (register int i = 2; i <= n; i++)  //一直筛到n
        for (register int j = i + i; j <= n; j += i)  //如果一个数是素数,那么它的倍数也一定是素数
            composite[j] = true;  //标记素数
}

注意这里：

for (register int j = i + i; j <= n; j += i)  //如果一个数是素数,那么它的倍数也一定是素数
         composite[j] = true;  //标记素数

这段代码在无脑的筛掉元素，为什么称它“无脑”呢？

对于同一个元素，埃筛可能会将它筛掉好多次。

埃氏筛时间复杂度：$O(n\log\log n)$

而接下来要介绍的欧拉筛的时间复杂度可以达到$O(n)$

算法思想

这里的欧拉筛全部以筛素数为例

对于一个合数，欧拉筛会确保它只被筛一次。

我们必须明确一下几点：

  1. 任何合数都可以表示为多个素数之积(唯一分解定理)
  2. 每个合数必有一个最小质因数

我们只需找出每个数的最小质因数即可。

先放一下代码，后面继续讲。

代码

void eulerSieve()
{
    composite[0] = true;
    composite[1] = true;
    for (register int i = 2; i <= n; i++)
    {
        if (!composite[i]) //是素数的话，我们就把它加入列表中
            ans[++num] = i;
        for (register int j = 1; j <= num && i * ans[j] <= n; j++)
        //i * ans[j] <= n 判边界
        {
            composite[i * ans[j]] = true;
            if (i % ans[j] == 0) // important!!!
                break;
        }
    }
}

由于一个素数乘上了一个其他的数就成了合数，而欧拉筛是要确保每个合数都只被筛一次，而且只能被它的最小质因数筛掉。我们把素数都存在ans数组里。

$ if(i \% ans[j] == 0) $说明$i$是$ans[j]$的倍数，我们设$ans[j]\times k=i$

我们反过来想，如果这里不退出的话，接下来会把$ans[j+1]\times i$这个数筛掉，而$ans[j+1]\times i$可以表示成$ans[j+1]\times k\times ans[j]$，说明$ans[j+1]\times i$是$ans[j]$的倍数，说明$ans[j+1]$不是最小最小质因数，再筛就重复了，所以要结束循环。

THE END