一种高科技做法：

$O(\log n)$ 判断素数：Miller Rabin算法

该算法的代码：（ $n值域[1,2^{32}]$ ）

inline long long ksm(long long a,long long b,long long p){
	long long res=1;
	while (b){
		if (b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

int bse[3]={2,7,61};

inline bool is_prime(long long n){
	if (n<3 || !(n&1)) return n==2;
	if (!(n%3)) return n==3;
	long long u=n-1, t=0;
	while (!(u&1)) u>>=1, t++;
	
	for (int i=0;i<=2;i++){
		long long a=bse[i]%n; if (a==0) continue; 
		long long v=ksm(a,u,n); if (v==1) continue;
		
		long long s=0;
		for (s=0;s<t;s++){
			if (v==n-1) break;
			v=v*v%n;
		}
		if (s==t) return 0;
	}
	return 1;
}

这样写是为什么呢？ 请看OIwiki （我太蒻了，不会证，但会用）

那么AC代码就显而易见了：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

using namespace std;

inline long long ksm(long long a,long long b,long long p){
	long long res=1;
	while (b){
		if (b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

int bse[3]={2,7,61};

inline bool is_prime(long long n){
	if (n<3 || !(n&1)) return n==2;
	if (!(n%3)) return n==3;
	long long u=n-1, t=0;
	while (!(u&1)) u>>=1, t++;
	
	for (int i=0;i<=2;i++){
		long long a=bse[i]%n; if (a==0) continue; 
		long long v=ksm(a,u,n); if (v==1) continue;
		
		long long s=0;
		for (s=0;s<t;s++){
			if (v==n-1) break;
			v=v*v%n;
		}
		if (s==t) return 0;
	}
	return 1;
}

long long a,b,c,d,e,f; 

int main(){
	
	srand((unsigned)time(0));
	while (scanf("%lld%lld",&a,&b)!=EOF){
		long long lst=-1, maxx=-1000000000000000,maxk1=-114514,maxk2=0, minn=100000000000000000,mink1=0,mink2=0;
		for (int i=a;i<=b;i++){
			if (!is_prime(i)) continue;
			
			if (lst==-1) {lst=i; continue;}
			
			if (maxx<i-lst){
				maxx=i-lst;
				maxk1=lst; maxk2=i;
			}
			if (minn>i-lst){
				minn=i-lst;
				mink1=lst; mink2=i;
			}
			lst=i;
			
		}
		if (maxk1==-114514){
			printf("-1\n");
			continue;
		}
		printf("%lld %lld %lld %lld\n",mink1,mink2,maxk1,maxk2);
	}
	return 0;
}

复杂度 $O(T (B-A)\log B)$

再在这里放几张图

首先我们考虑筛掉所有合数，因为 $B-A\leq 10^6$，所以我们筛掉合数之后就可以枚举了

首先筛出所有$1$ 到 $2^{16}$ 的所有质数，对于每一个质数 $p$ 枚举它的 $\left \lceil \frac{A}{p} \right \rceil \leq i \leq \left \lfloor \frac{B}{p} \right \rfloor $ 倍然后枚举

最后判断即可，注意 $1$ 不是质数！

	ola(N-10);
	while(scanf("%lld%lld",&A,&B)!=EOF){
		clr();
		for(int i=1;prime[i]*prime[i]<=B;i++){
			for(int j=ceil((double)A/prime[i]);j<=B/prime[i];j++){
				if(prime[i]!=prime[i]*j) vis[j*prime[i]-A+1]=1;
			}
		}
		for(int i=1;i<=B-A+1;i++){
			if(!vis[i]&&(i+A-1)!=1) ok[++ret]=i+A-1;
			if(ret>1){
				int now=ok[ret]-ok[ret-1];
				if(now<anss){
					anss=now,ans=ok[ret-1],bns=ok[ret];
				}else if(now==anss){
					if(ok[ret-1]<ans) ans=ok[ret-1],bns=ok[ret];
				}
				if(now>bnss){
					bnss=now,cns=ok[ret-1],dns=ok[ret];
				}else if(now==bnss){
					if(ok[ret-1]<cns) cns=ok[ret-1],dns=ok[ret];
				}
			}
		}
		if(ret<=1){
			puts("-1");
			continue;
		}
//		cout<<"ok:";
//		for(int i=1;i<=ret;i++) cout<<ok[i]<<" ";
//		puts("");
//		cout<<"vis:";
//		for(int i=1;i<=B-A+1;i++) cout<<vis[i]<<" ";
//		puts("");
		printf("%lld %lld %lld %lld\n",ans,bns,cns,dns);
	}