题解 P3912 【素数个数】

Aleph1022 · 2019-07-27 07:59:16 · 题解

我来一发 Min25 筛的题解！
（其实已经有一个大佬发了但是没什么解释

Min25 筛算法中有一个过程就是求 f 在质数处的值。
那么如果我们构造 f(n) = 1 那这个就相当于求质数的个数了。
（其实洲阁筛也有这一部分而且做法是一样的

设 G_k(n) = \sum\limits_{i=1}^n [p_k < \text{lpf}(i) \lor \text{isprime}(i)]，其中 p_k 表示第 k 小的质数，\text{lpf}(i) 表示 i 的最小质因子，\text{isprime}(i) 表示 i 是否为质数。
其实就是埃筛 k 轮之后剩下的数的个数。

考虑转移。
若 n < p_k^2，那么肯定不会筛掉任何一个数。
若 p_k^2 \le n，那么被筛掉的数必有质因子 p_k，故先减去 G_{k-1}\left(\left\lfloor\dfrac n{p_k}\right\rfloor\right)。
注意到这样子会减去 \text{lpf}(i) < p_k 的数，故加回 G_{k-1}(p_{k-1})。
整理一下可得

答案即 G_{cnt}(n)，其中 cnt 表示 \sqrt n 以内的质数个数。

观察转移式易得实际上用到的 G 的值都在所有 \left\lfloor\dfrac n i\right\rfloor 处，这样一共是 O(\sqrt n) 处，于是预处理一发即可。

复杂度被证明为 O(\frac{n^{3/4}}{\log n})（别问我怎么证，问就不知道

代码：

#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e8;
const int MX = 1e4;
int n;
int lim;
int vis[MX + 5],cnt,prime[MX + 5];
int lis[2 * MX + 5];
int tot,le[MX + 5],ge[MX + 5];
int G[2 * MX + 5];
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int main()
{
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            prime[++cnt] = i;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%d",&n),lim = sqrt(n);
    for(register long long l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        lis[id(n / l) = ++tot] = n / l;
        G[tot] = n / l - 1;
    }
    for(register int k = 1;k <= cnt;++k)
    {
        int p = prime[k];
        long long s = (long long)prime[k] * prime[k];
        for(register int i = 1;lis[i] >= s;++i)
            G[i] -= G[id(lis[i] / p)] - (k - 1);
    }
    printf("%d\n",G[1]);
}