本文共 785 字，大约阅读时间需要 2 分钟。

Prime Distance

题目

解析

发现$L$和$R$都大到不可做，但$R-L$却被限制在了$1000000$以内，考虑筛出$2$到$\sqrt{R}$内的质数，然后每次筛出$L$至$R$的合数，最后线性跑一下就好了

code:

#include
   
    #include
    
     #include
     
      using namespace std;int p[1000010],tot;long long l,r,a,b,c,d,la,mx,mn;bool v[1000010];int main(){
   	for(register int i=2;i<=1000000;i++)	{
   		if(!v[i])p[++tot]=i;		for(register int j=1;j<=tot&&i*p[j]<=1000000;){
   v[i*p[j]]=1;if(!(i%p[j++]))break;}	}	while(~scanf("%lld%lld",&l,&r))	{
   		memset(v,1,sizeof(v)),v[0]=(l!=1),la=mx=0,mn=1000000000000000000ll;		for(register int i=1;i<=tot;++i)for(register long long j=l/p[i];j*p[i]<=r;++j)if(j>1&&j*p[i]>=l)v[j*p[i]-l]=0;		for(register long long i=l;i<=r;++i)if(v[i-l]){
   if(la){
   if(mn>i-la)mn=i-la,a=la,b=i;if(mx
     
    
   

转载地址：https://blog.csdn.net/zhanglili1597895/article/details/118054174 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！