素数密度

分析：

本题 $L$ 和 $R$ 的范围太大，数组就存不下，所以可以先处理出 $[L-\sqrt{R}]$ 间的小质数，再去推导出之后的质数。

实现：

对于质数表(其中质数为 $p$ )，起点为 $$max(p*p,((L+p-1)/p)*p)$$
其中，$p*p$ 自然是该质数的平方，$((L+p-1)/p)*p$ 则是 $\lceil \frac Lp \rceil$ 即大于等于 $\frac Lp$ 的最小整数，以该质数 $p$ 为步长遍历到 $R$ ，别忘了下标减去 $L$ ，这样就将合数筛出去了。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int l,r;
vector<int>a;
void f(int x)
{
    vector<bool>st(x+1,false);
    st[0]=st[1]=true;
    for(int i=2;i<=x;i++)
    {
        if(!st[i])a.push_back(i);
        for(auto &w:a)
        {
            if(w*i>x)break;
            st[w*i]=true;
            if(i%w==0)break;
        }
    }
}
signed main()
{
 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 cin>>l>>r;
 int x=sqrt(r)+1;
 f(x);
 vector<bool>vis(r-l+1,true);//这才是最终的表 
 for(auto &p:a)
 {
  int start=max(p*p,((l+p-1)/p)*p);
  for(int j=start;j<=r;j+=p)
  vis[j-l]=false;   
 } 
 //特判 
 if(l==1)vis[0]=false;
 int cnt=0;
 //for(auto &w:vis)if(w)cnt++;
 for(int i=0;i<vis.size();i++)if(vis[i])cnt++;
 cout<<cnt;
 return 0;  
}