素数筛【含算法原理和详细证明】

前置知识：

• 自然数按因数的个数分：质数、合数、$0$、$1$ 四类

• 最小的质数是 $2$，最小的合数是 $4$，连续的两个质数是 $2$、$3$

• 每个合数都可以由几个质数相乘得到，即合数等于质数之积，质数相乘一定得到合数

• 除了 $2$ 和 $5$，其余质数的个位都是 $1、 3、 7、 9$

• 质数定理：当 $n \rightarrow \infty$ 时，$1\sim n$ 中的质数个数为 $\dfrac{n}{\ln n}$。

常用筛法：

1、暴力筛 $O(n\sqrt n)$

通过用判断素数的函数来枚举每一数加入到素数表中。

int primes[N], cnt;
bool is_primes(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
            return false;
    return true;
}

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
        if (is_prime(i)) primes[cnt ++ ] = i;
}

时间复杂度分析：

遍历 $O(n)$，素数判断最坏 $O(\sqrt n)$，总复杂度为 $O(n\sqrt n)$。

2、朴素筛 $O(n\log n)$

任何整数 $x$ 的倍数 $2x, 3x, \cdots$ 都不可能是素数。我们可以从 $2$ 往后扫描，将当前数的所有倍数全部筛掉，剩下没有被筛掉的数就是质数。

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i ) st[j] = true;
    }
}

时间复杂度分析：

当 $i = 2$ 时，第二层循环共循环了 $\dfrac{n}{2}$ 次，$i = 3$ 时循环了 $\dfrac{n}{3}$ 次，$\cdots$，总共循环了： $$\dfrac{n}{2} + \dfrac{n}{3} + \cdots + \dfrac{n}{n} = n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})$$ 其中 $\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n}$ 为调和级数，当 $n \rightarrow \infty$ 时，有：$\sum\limits_{k=1}^{n} \dfrac{1}{k} = \ln n + \gamma$，并且 $\gamma$ 为欧拉常数（$\text{Euler Constant}$），约为 $0.577215664\ldots$ 故时间复杂度： $$n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})\approx n\ln n \approx n\log n$$ 即 $O(n\log n)$。

3、 埃拉托斯特尼（埃氏）筛 $O(n\log \log n)$

对上面的朴素筛法进行优化，我们发现并不需要将每个数的倍数都筛去，我们可以只把所有质数的倍数筛去。

若按照之前的筛法筛去一个整数的所有倍数，我们最终会留下一些质数，以 $p$ 为例，说明 $p$ 不是 $2\sim p - 1$ 内任何一个数的倍数，我们并不需要将 $2\sim p - 1$ 内所有的数依次枚举一遍，只要将其中的质数枚举一遍即可，因为合数等于质数之积。

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i ) st[j] = true;
        //  for (LL j = (LL)i * i; j <= n; j += i ) st[j] = true;
        }
}

这里有个优化，$j$ 可以从 $i\cdot i$ 开始枚举，因为 $i\cdot (2\sim i - 1)$ 已经被 $2\sim i - 1$ 筛去了。但由于数据范围限制，这样会使得 $i\cdot i$ 可能会爆 int，因此要开 long long。

时间复杂度分析：

由于我们只用筛去 $2\sim n - 1$ 中的素数倍数即可，故调和级数变为：$\sum\limits_{p\leq n} \dfrac{1}{p}$，其中 $p$ 为质数。当 $n$ 趋于无穷时，有：

$$M = \lim_{n\to \infty} \left (\sum\limits_{p\leq n} \dfrac{1}{p} - \ln(\ln(n))\right) = \gamma + \sum\limits_p \left [\ln \left(1 - \dfrac{1}{p} \right) + \dfrac{1}{p} \right]$$

其中，$M$ 为 $\text{Meissel-Mertens}$ 常数，也称 $\text{Mertens}$ 常数或质数倒数和常数，数值约为 $0.261497\ldots$

所以当 $n\rightarrow \infty$ 时，$n\cdot \sum\limits_{p\leq n} \dfrac{1}{p} \approx n\ln(\ln n)$，即为 $O(n\log \log n)$。

4、 线性（欧拉）筛 $O(n)$

埃氏筛存在一个缺陷，即对于一个合数，可能会被筛多次，例如 $30 = 2\times 15 = 5\times 6\ldots$，我们改用其最小质因子去筛掉这个合数，就可以保证他只会被筛一次。

我们从小到大枚举所有质因子 primes[j]。

1、当出现 i % primes[j] == 0 时，primes[j] 一定是 $i$ 的最小质因子，因此也一定是 primes[j] * i 的最小质因子。

2、当出现 i % primes[j] != 0 时，说明我们还尚未枚举到 $i$ 的任何一个质因子，也就表示 primes[j] 小于 $i$ 的任何一个质因子，这时 primes[j] 就一定是 primes[j] * i 的最小质因子。

可以发现无论如何，primes[j] 都一定是 primes[j] * i 的最小质因子，并且由于所要筛的质数在 $2\sim n$ 之间，因此合数最大为 $n$，故 primes[j] * i 只需枚举到 $n$ 即可，但由于 primes[j] * i 可能会溢出整数范围，故改成 primes[j] <= n / i 的形式。

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)  break; // primes[j] 一定是 i 的最小质因子 
        }
    }
}

时间复杂度分析：

$2\sim n$ 中，任何一个合数都会被筛去，而且仅用最小质因子去筛，每个合数都有且仅有一个最小质因子，故每个合数只会被筛一次，所以时间复杂度为 $O(n)$。

完整代码：

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

bool st[N];
int primes[N], cnt, n;

void get_primes(int n) 
{
    ...
}

int main()
{
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}