【算法学习笔记】30：埃氏筛（Sieve of Eratosthenes）和线性筛（Linear Sieve）

测试题目：AcWing 868. 筛质数

埃氏筛（Sieve of Eratosthenes）

如果$i$是素数，每次把$i$的倍数都筛掉，存在重复筛选，时间复杂度$n\cdot log(logn)$。

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, cnt = 0;
bool st[N]; // false as prime

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        cnt ++ ;
        for (int j = i * 2; j <= n; j = j + i)
            st[j] = true;
    }
    cout << cnt << endl;
    
    return 0;
}

线性筛（Linear Sieve）

也叫欧拉筛，在埃氏筛的思想下，想办法让每个合数只被筛出去一次，消除重复筛选，这样时间复杂度就能降低到$O(n)$。

为了让每个合数$a$只被筛出去一次，由于我们是从小到大筛选质数的，因此可以考虑让这个合数$a=a_1\cdot a_2\cdot ...\cdot a_k$由其最小的质因数$a_1$筛掉。

因此每次遍历到一个数$i$，不论是质数或者合数，其最小质因数如果是$r$，那么由于我们从小到大筛到了$i$，所以质数$r$一定已经在目前的质数结果集里了（被筛好了）。

进而，所有$<r$的质数都已经被筛好了，我们可以对于每个$<=r$的质数$x$，把$x\cdot i$筛掉，那么因为$x\cdot i$的最小质因数一定是$x$，所以理应在（且仅在）这一轮被筛掉。

然而，知道每个数$i$的最小质因数$r$是困难的，但反正我们都要拿它每个$<=r$的质数$x$去筛掉$x\cdot i$了，每次筛掉之后看一下质数$x$是不是$i$的因数就可以了，因为我们是从小到大遍历质数$x$的，所以$x$第一次成为$i$的因数的时候，$x$就是$i$的最小质因数，这时候就可以停止筛了。

如果没有停止筛会有什么问题？重复筛选导致的算法退化！试想应在$x$是$i$的因子时停止，最后一轮筛掉的就是$x\cdot i$，如果没有停下来，又取了下一个质数$x^{\prime }$，筛掉了$x^{\prime }\cdot i$。因为$i$的最小质因数就是$x$，所以$x^{\prime }\cdot i$这个数应该在先前就被质数$x$以$x\cdot \frac{i\cdot x^{\prime }}{x}$的模式筛过了！

写法上应该注意，线性筛不是像埃氏筛那样，只在发现质数的轮次筛合数，而是在每个轮次$i$，不管最小质因数是$r$的当前轮次$i$是不是质数，都用$<=r$的所有质数$x$去筛$x\cdot i$，以保证每个数都仅被其最小质因数筛掉。

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int primes[N];
int n, cnt = 0;
bool st[N]; // false as prime

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int x = primes[j];
            st[x * i] = true;
            if (i % x == 0) break;
        }
    }
    cout << cnt << endl;
    
    return 0;
}