题意：给出一个区间[L,U]，找出区间里相邻的距离最近的两个素数和距离最远的两个素数。

用素数筛选法。

所有小于U的数，如果是合数，必定是某个因子(2到sqrt(U)间的素数)的倍数。

由于sqrt(U)最大也只有2^16，所以我们可以用素数筛选法，先预处理出2~2^16之间的素数，然后再用这些素数筛选出L~U之间的素数。

接着就好办了。

有几个要注意的是：

1:L为1的情况，可以通过令L=2或者标记isp[0]=false。

2:建议用long long，否则很容易在过程中超int范围，导致数组越界RE。。。

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=(1<<16)+5;const int range=1000000+5;bool isprime[maxn]; //标记2~2^16之间的素数bool isp[range];  //标记L~U之间的素数，下标从0开始，对应L。int prime[maxn]; //存储2~2^16之间的素数int idx;long long L,U;void init(){    idx=0;    memset(isprime,true,sizeof(isprime));    for(int i=2;i
         
          1){                    isp[j*p-L]=false;                }            }        }        int mina,minb,mindis=2000000,maxa,maxb,maxdis=0;        int a,b;        bool first=true;        for(int i=0;i<=U-L;i++){            if(isp[i]){                if(!first){                    b=i;                    if(b-a
          
           maxdis){                        maxa=a;                        maxb=b;                        maxdis=b-a;                    }                    a=b;                }                else{                    first=false;                    a=i;                }            }        }        if(!maxdis){            printf("There are no adjacent primes.\n");        }        else{            //注意：这里输出时long long格式，因为L是long long型            printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",mina+L,minb+L,maxa+L,maxb+L);        }    }    return 0;}