luogu质数距离

解法

已知sqrt（n）内的质数即可筛出n内的
因为L到R十分小，所以先求出sqrt内的，再用这些去埃氏筛L到R的。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e7+5;

int v[N],prime[N],b[N];
int L,R,ans,num;

int read()
{
    int x=0,p=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') p=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*p;
}
    
main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

    L=read(),R=read();
    int st=sqrt(1UL<<31);
    for(int i=2;i<=st;i++)
    {
        if(!v[i]) { v[i]=i,prime[++num]=i; }

        //给当前的数i乘一个质因子
        for(int j=1;j<=num;j++)
        {
            if(prime[j]>v[i] || prime[j]>st/i) break ;
            v[i*prime[j]]=prime[j];
        }
    }

	for(int i=1;i<=num;i++)
	{
		if(prime[i]>R) break ;
		int l=ceil((double)L/prime[i])*prime[i];
		if(l==prime[i]) l+=prime[i];
		for(int j=l;j<=R;j+=prime[i])
			b[j-L]=1; 
	}
	for(int i=L;i<=R;i++) if(!b[i-L]) ans++;

    cout<<ans<<endl;

    //for(int i=1;i<=num;i++) printf("%d ",prime[i]);
    return 0;
}

不开long long卡了一个多小时。。。。