Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 29401 Accepted: 7556
Description
Input
Output
Sample Input
2 17 14 17
Sample Output
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
题意：在区间[L,U]中找出一对距离最近的相邻素数和一对距离最远的相邻素数，距离相同时，取第一对。
题解：区间素数筛。由于数据范围太大，无法用数组维护素数。用区间[1，]的素数去更新区间[L，U]的素数。(用已知小范围素数推未知大范围素数)。区间间差不超多1000000，利用下标偏移,区间[0,U-L]维护区间[L,U]。
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
int prime[5000],top;
bool flag[50005]={1,1},isp[1000005];
void init();
void solve(int L,int R);
int main()
{
init();
int L,R,l1,r1,l2,r2,i,j,mmin,mmax;
while(~scanf("%d%d",&L,&R))
{
if(L==1) L=2; //重要
{
fill(isp,isp+1000005,1);
mmin=inf;mmax=-inf;
}
solve(L,R);
for(i=0;i<=R-L;i++)
{
if(!isp[i]) continue;
for(j=i+1;j<=R-L;j++)
if(isp[j])
{
if(mmax<(j-i)) mmax=j-i,l1=i+L,r1=j+L;
if(mmin>(j-i)) mmin=j-i,l2=i+L,r2=j+L;
break;
}
}
if(mmax==-inf) printf("There are no adjacent primes.\n");
else printf("%d,%d are closest, %d,%d are most distant.\n",l2,r2,l1,r1);
}
return 0;
}
void init()
{
int i,j;
for(i=2;i<50005;i++)
{
if(!flag[i]) prime[top++]=i;
for(j=0;j<top&&i*prime[j]<50005;j++)
{
flag[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void solve(int L,int R)
{
long long i,l;
for(i=2;i*i<=R;i++)
{
if(flag[i]) continue;
for(l=max(2LL,((i+L-1)/i))*i;l<=R;l+=i) isp[l-L]=0;
}
}
原文：https://www.cnblogs.com/VividBinGo/p/11390629.html