题意：给区间[L,U]，要求该区间内，距离最小的素数对，和距离最大的素数对，输出素数对和对应距离。（距离的定义：2个相邻素数的差的绝对值）
分析：
1、筛选法
2、由于区间L,U (1<=L< U<=2,147,483,647)本身可能很大，直接筛选数组都开不下。
但是题目说“The difference between L and U will not exceed 1,000,000.”也就是说U-L<=1000 000,这就给我们启示只筛选区间内部的素数。
然后由于区间是一个连续区间，所以我们用x(L=<x<=U)%1000000就可以把x映射到1000 000内的数了。这样开一个1000 000的数组存素数就好（当然，区间内的素数肯定没这么多）
3、注意用long long因为筛选过程可能超int（嘛……如果用int的话，本地都应该跑不出来才对吧……前提是自己随便输一个大一点的数……我也是程序死循环了才改的……T T）
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<map>
5 #include<string>
6 using namespace std;
7 const int MAXN = 50001;
8 const int MOD = 1000001;
9 int prime[MAXN];
10 int isprime[MAXN*20];
11 int prim[MAXN*20];
12 int init(){
13 int k = 0;
14 memset(prime,0,sizeof prime);
15 for(int i = 2;i<MAXN;i++){
16 //cout<<"\n"<<i<<endl;
17 if(!prime[i]){
18 prime[k++] = i;
19 long long j = (long long )i*(long long )i;
20 //cout<<j<<endl;
21 for(;j<MAXN;j+=i)prime[j] = 1;
22 }
23 }
24 return k;
25 }
26 int shaixuan(long long L,long long U,int pn){
27 memset(isprime,0,sizeof isprime);
28 //cout<<prime[0]<<"\nU:"<<U<<endl;
29 for(long long i = 0;prime[i]<U+1 && i<pn;i++){
30 //cout<<"???\n";
31 long long tp = L/prime[i];
32 if(tp < 2) tp = (long long )prime[i]*(long long )prime[i];
33 else{
34 tp = tp*(long long )prime[i];
35 if(tp < L)tp+=(long long )prime[i];
36 }
37 //cout<<prime[i]<<" "<<tp<<"\n";
38 //if(!isprime[tp%MOD]){
39 //cout<<tp%MOD<<endl;
40 for(long long j = tp;j<U+1;j+=(long long )prime[i]){
41 isprime[j%MOD] = 1;
42 }
43 //}
44 }
45 int k = 0;
46 for(long long i = L;i<U+1;i++){
47 if(i == 1)continue;
48 if(!isprime[i%MOD]){
49 prim[k++] = i;
50 //cout<<i<<endl;
51 }
52 }
53 return k;
54 }
55 int main()
56 {
57 #ifdef LOCALL
58 // freopen("in.txt","r",stdin);
59 // freopen("out.txt","w",stdout);
60 #endif
61 int pn = init();
62 int L,U;
63 while(cin>>L>>U){
64 if(U == 1 || U == 2){cout<<"There are no adjacent primes."<<endl;continue;}
65 int pn2 = shaixuan(L,U,pn);
66 if(pn2 == 1){cout<<"There are no adjacent primes."<<endl;continue;}
67 long long minn ,maxn = 0,minx,maxx;
68 minx = maxx = 0;
69 minn = 1<<30;
70 //cout<<pn2<<endl;
71 //cout<<minn<<endl;
72 for(int i = 1;i<pn2;i++){
73 // cout<<"prim["<<i<<"]:"<<prim[i]<<endl;
74 //cout<<"sub:"<<prim[i]-prim[i-1]<<endl;
75 if(prim[i]-prim[i-1] < minn) {minn = prim[i]-prim[i-1]; minx = i-1;}
76 if(prim[i]-prim[i-1] > maxn) {maxn = prim[i]-prim[i-1]; maxx = i-1;}
77 }
78
79 //cout<<"min:"<<minn<<" maxx:"<<maxn<<"maxx:"<<maxx<<endl;
80 cout<<prim[minx]<<","<<prim[minx+1]<<" are closest, "<<prim[maxx]<<","<<prim[maxx+1]<<" are most distant.\n";
81
82 }
83 return 0;
84 }
总之，筛选法简直打素数表之万能神器……