【YBTOJ】质数距离

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    
    long long l, r;
    long long tot, a[10001000];
    long long prim[10010000], v[10001000];
    long long bz[10010000];
    
    void prime(long long n)
    {
    	for(long long i=2; i<=n; i++)
    	{
    		if(v[i]==0)
    		{
    			prim[++tot]=i;
    			v[i]=i;
    		}
    		for(long long j=1; j<=tot&&prim[j]*i<=n; j++)
    		{
    			v[prim[j]*i]=prim[j];
    			if(i%prim[j]==0)
    				break;
    		}
    	}
    }
    
    int main()
    {
    	prime(5000000);
    	while(cin>>l>>r)
    	{
    		if(l==1)
    			l++;
    		memset(bz, 0, sizeof(bz));
    		for(long long i=1; i<=tot; i++)
    		{
    			for(long long j=l/prim[i]; j<=r/prim[i]; j++)	
    				if(j>1&&j*prim[i]-l>=0)
    					bz[j*prim[i]-l]=1;
    		}
    		long long tmp=0;
    		for(long long i=l; i<=r; i++)
    			if(bz[i-l]==0)
    				a[++tmp]=i;
    		long long ans1=a[2]-a[1], ans2=a[2]-a[1], maxq1=a[1], maxq2=a[2], minq1=a[1], minq2=a[2];
    		for(long long i=3; i<=tmp; i++)
    		{
    			if(a[i]-a[i-1]>ans1)
    				ans1=a[i]-a[i-1], maxq1=a[i-1], maxq2=a[i];
    			if(a[i]-a[i-1]<ans2)
    				ans2=a[i]-a[i-1], minq1=a[i-1], minq2=a[i];
    		}
    		if(tmp<2)
    			printf("There are no adjacent primes.\n");
    		else
    			printf("%lld,%lld are closest, %lld,%lld are most distant.\n", minq1, minq2, maxq1, maxq2);
    	}
    	return 0;
    }