改了一下午,吐了
#include <bits/stdc++.h>
#define int long long
using namespace std;
class Dis
{
public:
int d,l,r;
}minn,maxn;
bool prime[1000001],vis1[1000001],vis2[1000001];
int make1[1000001],make2[1000001];
int ans,cnt1,cnt2;
void linear_prime_build(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if (!vis1[i]) make1[++cnt1]=i,prime[i]=true;
for(j=1;j<=cnt1 && i*make1[j]<=n;j++)
{
vis1[i*make1[j]]=true;
if (i%make1[j]==0) break;
}
}
}
void re_title()
{
memset(prime,false,sizeof(prime));
memset(vis1,false,sizeof(vis1));
memset(vis2,false,sizeof(vis2));
memset(make1,false,sizeof(make1));
memset(make2,false,sizeof(make2));
ans=cnt1=cnt2=0;
}
signed main()
{
//素数距离
int L,R,k,tL,i,j;
while(scanf("%lld%lld",&L,&R)!=EOF)
{
re_title();
minn=(Dis){INT_MAX,INT_MAX,INT_MAX};
maxn=(Dis){INT_MIN,INT_MIN,INT_MIN};
if (L==1) L=2;
linear_prime_build(100000);
for(i=1;i<=cnt1;i++)
{
k=make1[i];
tL=max(k*2,(L+k-1)/k*k);
for(j=tL;j<=R;j+=k) vis2[j-L+1]=true;
}
for(i=1;i<=R-L+1;i++)
if (!vis2[i]) make2[++cnt2]=i+1;
// for(i=1;i<=cnt2;i++) printf("%lld ",make2[i]);
// printf("\n");
if (cnt2<=2)
{
printf("There are no adjacent primes.\n");
return 0;
}
for(i=2;i<=cnt2;i++)
{
int d=make2[i]-make2[i-1];
if (d<minn.d) minn=(Dis){d,make2[i-1],make2[i]};
if (d>maxn.d) maxn=(Dis){d,make2[i-1],make2[i]};
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minn.l,minn.r,maxn.l,maxn.r);
}
}