自动搬运

查看原文

来自洛谷，原作者为

	Segmentree Respect

搬运于2025-08-24 21:30:52，当前版本为作者最后更新于2019-07-28 21:08:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

巨简单易懂的题解[连我都看得懂还有谁看不懂]

首先来看下数据范围[L，R] (L≤R≤2147483647,R-L≤1000000)

极值最大有20亿,因此O(N)的暴力筛会瞬间爆炸

再仔细看看题

题目要我们筛出L-R范围内的素数,那么我们只要将这个区间中的合数踢出去不就结束了吗w

说起判断合数,我就想到了美猴王合数的一个性质:可以分解为两个不为1且不等于本身的因子相乘 即 n=a*b(n为合数).下证之:

• 设a<=b 则a * a<a*b
• 又因a* b=n,则a* a<=n*n
• 即a<=
• 因此,在1-的范围之中我们必能找到n的一个质因子
• 所以,我们只需要在1-范围中筛出所有的质数(剩下的即为合数),然后用我们已经筛出来的因子去在L-R的范围中求出所有的合数,剩下来的即为我们要找的质数,而R的最大值大约为20亿,所以我们只用求(1-50000中的质数就可以拿他们来玩耍使用了!)

有了思路之后这道题就很简单了,大概流程如下

1. 筛出1-50000中的所有质数,并且对合数打上标记.
2. 在L-R的范围呢用我们已求出的质数筛出其中的合数(设p为质数,则i*p一定不为质数),并对其打上标记
3. 遍历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;
}

算法的速度还是比较优秀的,不吸氧和吸氧羊都是65ms的样子

谢谢观看qwq