学步园

       和1~n范围内筛素数差不多...只不过对于每个素数加了一个偏移量了..比如在5 10这个区间..筛掉2的倍数..那么从6开始剔除...由于题目所给的数据..最大的合数..其质因子不会大于10^5..所以先用传统的筛素数法把1~10^5内的素数找出..然后再来筛[L,U]这个区间的素数...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long 
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 1000005
using namespace std;
ll Prime[MAXN],ans[MAXN];
int Pnum,anum;
bool P[MAXN];
void PreWork()
{
       int i,x;
       memset(P,true,sizeof(P)); 
       for (Pnum=0,i=2;i<=100000;i++)
          if (P[i])
            for (Prime[++Pnum]=i,x=i*2;x<=100000;x+=i)
               P[x]=false; 
}
int main()
{  
       PreWork(); 
       for (ll L,U;~scanf("%I64d%I64d",&L,&U);)
       {
                ll n=U-L;
                memset(P,true,sizeof(P));
                for (int i=1;i<=Pnum;i++)
                {
                       ll h=Prime[i],x;
                       if (h*h>U) break;
                       x=(h-(L%h))%h;
                       if (L+x==h) x+=h;
                       for (;x<=n;x+=h) P[x]=false;
                }
                if (L==1) P[0]=false;
                anum=0;
                for (int i=0;i<=n;i++)
                   if (P[i]) ans[++anum]=i+L;
                if (anum<2) printf("There are no adjacent primes.\n"); 
                   else 
                {
                      int i,a,b;
                      a=b=1;
                      for (i=1;i<anum;i++)
                      {
                           if (ans[i+1]-ans[i]<ans[a+1]-ans[a]) a=i;
                           if (ans[i+1]-ans[i]>ans[b+1]-ans[b]) b=i;
                      }
                      printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",ans[a],ans[a+1],ans[b],ans[b+1]);
                }
       }
       return 0;
}