这是一道较为著名的数论题
「一本通 6.2 例 1」Prime Distance
题目描述
原题来自：Waterloo local，题面详见 POJ 2689
给定两个整数 L,R ，求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。
输入格式
多组数据。每行两个数 L,R。
输出格式
详见输出样例。
样例
输入数据 1
2 17
14 17
输出数据 1
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
数据范围与提示
对于全部数据，1≤L<R<2^31 ,R−L≤10^6
上课讲过了，回家想了想敲了个49行代码，结果……不说了，看完代码再说吧
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
void eth(int l,int r);
int ss[9]={0,2,3,5,7,11,13,17,37},ans,l,r,maxi,mini;
pii maxo,mino;
int main(){
while(cin>>l>>r){
eth(l,r);
if(mini==0x3f3f3f3f)
puts("There are no adjacent primes.");
else
printf("%d,%d are closest, %d,%d are most distant.\n",mino.x,mino.y,maxo.x,maxo.y);
}
}
void eth(int l,int r){
int sum=0,fi;
bool ks=0;
mini=0x3f3f3f3f;
for(int i=max(l,2);i<=r;i++){
bool k=1;
for(int j=1;j<=8;j++)
if(ss[j]!=i&&i%ss[j]==0){
k=0;
sum++;
break;
}
if(k&&ks){
if(sum<mini){
mini=sum;
mino=pii(fi,i);
}
if(sum>maxi){
maxi=sum;
maxo=pii(fi,i);
}
sum=0;
fi=i;
}
else if(k)
ks=1,fi=i;
}
}
猜到了吧，TLE了
就一个测试点，还加了O2，有人能帮帮我吗？
