Sample Input
2 17
14 17
Sample Output
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
找出给定范围内，距离最远和最近的素数。（不停超时 - -）
给的上界很大，所以全处理肯定不行。 先处理sqrt（2147483647）。
然后再在l 与 r之间筛选素数。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 10100
typedef long long ll;
using namespace std;
int n,m;
int f[1000500];
int q[1000500];
int t[100050];
int tot;
void prim()
{
ll i,j;
for(i = 2; i <= 100050; i++)
q[i] = 1;
for(i= 2,tot = 0; i <= 100050; i++)
{
if(q[i])
{
t[tot++] = i;
for(j = i*2; j <= 100050; j+=i)
q[j] = 0;
}
}
} int main()
{
int l,r;
while(scanf("%d%d",&l,&r)!= EOF)
{
prim();
if(l == 1)
l = 2; memset(f,0,sizeof(f));
for(int i =0; i < tot; i++)
{
int a = (l-1)/t[i]+1;
int b = r /t[i];
for(int j = a; j <= b; j++) //类似上面prim（）的方法
if(j > 1)
f[j*t[i]-l] = 1;
}
int Max = -1;
int Min = 1000000000;
int tmp = -1;
int maxl,maxr,minl,minr; for(int i = 0; i <= r-l; i++)
{
if(!f[i])
{
if(tmp>=0 && i - tmp> Max)
{
Max = i-tmp;
maxl = tmp+l;
maxr = i+l;
}
if(tmp>=0 && i - tmp< Min)
{
Min = i-tmp;
minl = tmp+l;
minr = i+l;
}
tmp = i;
}
}
if(Max == -1)
printf("There are no adjacent primes.\n");
else
{
printf("%d,%d are closest, %d,%d are most distant.\n",minl,minr,maxl,maxr);
}
}
return 0;
}