https://oj.shiyancang.cn/Problem/781.html

素数距离，数据范围21亿，如果用素数筛存，并且进行做的话，按照x/lnx计算会是一个非常恐怖的复杂度。确定要做什么，首先一定要筛选素数，然后一定要进行素数的比较。问题就在筛选素数这里，可以看到区间范围很小，可以从这里入手，怎么储存，不可能按照那个储存，可以进行离散化，或者偏移，等等注意1的存在，无法被素数筛选掉，注意越界问题，那么就是区间素数筛选，埃氏筛的使用。因为算数基本定理，必然有小于sqrt的素数因子，这是可以接受的。那么sqrt再x、lnx就会很小了，每次一个1e4的复杂度直接解决了，求出a，b.储存上一状态的量，逐一比较即可。

#include
using namespace std;
typedef long long ll;
const ll N=1e5+520;
const ll INF=0x3f3f3f3f;
ll prime1[N],cnt,prime2[N*10],l,r;
bool st[N*10];
void get_prime(ll n)
{
for(int i=2;i<=n;i++) { if(!st[i]) prime1[cnt++]=i; for(int j=0;prime1[j]<=n/i;j++) { st[prime1[j]*i]=1; if(i%prime1[j]==0) break; } } } void get_prime2() { ll a,b; memset(st,0,sizeof(st)); for(ll i=0;i1)
{
st[prime1[i]*j-l]=1;
}
} //压缩储存，区间长度很小
}
if(l==1) st[0]=1;
}
void solve ()
{
ll minn=INF,maxn=-INF;
ll minl,minr,maxl,maxr;
get_prime2();
ll p=-1;
for(int i=0;i<=r-l;i++) { if(!st[i])//只需要记录前面和后面就可以了 { if(p!=-1) { if(maxni-p) minn=i-p,minl=p,minr=i;
}
p=i;//每次做完都要更新，而不是第一次更新，因为相邻
}
}
//通过状态有没有更新，来判断是否具有结果
if(maxn==-INF)printf("There are no adjacent primes.\n");
else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minl+l,minr+l,maxl+l,maxr+l);
// if(cnt2<=1) cout<<"There are no adjacent primes.\n"; // else // { // for(int i=0;imaxn)
// {
// maxn=prime2[i+1]-prime2[i];
// maxl=prime2[i],maxr=prime1[i+1];
// }
// }
// printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minl,minr,maxl,maxr);
// }
}
int main()
{
get_prime(N);
while(~scanf("%lld%lld",&l,&r))solve();
return 0;
}