题解 P1835 【素数密度_NOI导刊2011提高（04）】
Segmentree · · 题解
巨简单易懂的题解[连我都看得懂还有谁看不懂]
首先来看下数据范围[L，R] (L≤R≤2147483647,R-L≤1000000)
极值最大有20亿,因此O(N)的暴力筛会瞬间爆炸
再仔细看看题
题目要我们筛出L-R范围内的素数,那么我们只要将这个区间中的合数踢出去不就结束了吗w
说起判断合数,我就想到了美猴王合数的一个性质:可以分解为两个不为1且不等于本身的因子相乘
即 n=a*b(n为合数).下证之:
- 设a<=b 则a a<ab
- 又因a b=n,则a a<=n*n
- 即a<=
- 因此,在1-的范围之中我们必能找到n的一个质因子
- 所以,我们只需要在1-范围中筛出所有的质数(剩下的即为合数),然后用我们已经筛出来的因子去在L-R的范围中求出所有的合数,剩下来的即为我们要找的质数,而R的最大值大约为20亿,所以我们只用求(1-50000中的质数就可以拿他们来
玩耍使用了!)
有了思路之后这道题就很简单了,大概流程如下
- 筛出1-50000中的所有质数,并且对合数打上标记.
- 在L-R的范围呢用我们已求出的质数筛出其中的合数(设p为质数,则i*p一定不为质数),并对其打上标记
- 遍历L-R,没有打标记的元素即为我们所求的素数
代码如下
/*Coded By Lxhao*/
/*Full Of Stars*/
#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
const int maxn=1e6+1;
ll l,r;
int prime[maxn],cnt,ans;
bool vis[maxn];
inline void Gprime()//线性筛素数,预处理根号R内的素数,这里不赘述了,dalao们肯定都会qwq
{
for(re int i=2;i<=50000;++i)
{
if(!vis[i])prime[++cnt]=i;
for(re int j=1;i*prime[j]<=50000;j++)
{
vis[i*prime[j]]=1;//标记合数
if(i%prime[j]==0) break;
}
}
}//50000的范围很小即使不用线性筛用根号N的筛法也能过
int main()
{
ios::sync_with_stdio(false);//读入加速(在freopen下不可用!!!)
cin>>l>>r;
l=l==1?2:l;//特判L=1的情况
Gprime();//筛出根号R内的所有质数以及剩下的合数
memset(vis,0,sizeof(vis));//懒得多开一个数组,沿用函数中的数组时记得清空
for(re int i=1;i<=cnt;++i)//枚举已经筛出来的质数
{
ll p=prime[i],start=(l+p-1)/p*p>2*p?(l+p-1)/p*p:2*p;//我们从大于L的最小的能被p整除的数开始,(l+p-1)就等于ceil(l+p-1),因为有可能会在接下来筛的过程中把自己也一起筛掉,所以在此特判一下
for(re ll int j=start;j<=r;j+=p)vis[j-l+1]=1;//因为如果从j开始标记的话可能会爆vis的空间,所以我们这里从1开始标记合数,原理在上面已经叙述过了
}
for(re int i=1;i<=r-l+1;++i)if(!vis[i])ans++;//r-l+1即为区间长度,遍历区间找没有被标记的元素并累加答案
cout<<ans;
}