洛谷P1835 素数密度 题解

题目链接：P1835 素数密度

题意：

给定 $L,R$，请计算区间 $[L,R]$ 中素数的个数。

输入格式：

第一行，两个正整数 $L$ 和 $R$。

输出格式：

一行，一个整数，表示区间中素数的个数。

数据范围：

$1\leq L\leq R < 2^{31}$，$R-L\leq 10^6$。

z注意到 $\sqrt{R}$ 只有约 $V=50000$ 的数量级

我们可以预处理出小于 $50000$ 的质数，然后用这些质数暴力埃氏筛。

时间复杂度 $\mathcal{O}\left(\frac{V}{\ln V} \log (R-L)\right)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int _ = 50000;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

char ck[N], vis[N]; int pcnt, pri[N];
void init()
{
    for(int i = 2; i <= _; i++)
    {
        if(!ck[i]) pri[++pcnt] = i;
        for(int j = 1; j <= pcnt && pri[j] * i <= _; j++) {
            ck[pri[j] * i] = true; if(i % pri[j]) break;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int l, r; cin >> l >> r; init(); if(l == 1) l = 2;
    for(int i = 1; i <= pcnt; i++)
    {
        int &p = pri[i], o = max((l + p - 1) / p * p, 2 * p);
        for(int j = o; j <= r; j += p) vis[j - l + 1] = true;
    }
    int res = 0;
    for(int i = l; i <= r; i++) res += (!vis[i - l + 1]);
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/arizrqsd

---

题外话：

都说了早上脑子不好使了啦。