POJ

题意：求[L,R]中差值最小和最大的相邻素数(区间长度不超过1e6)。

由于非素数$n$必然能被一个不超过$sqrt n$的素数筛掉，因此首先筛出$[1,sqrt R]$中的全部素数，然后用这些素数去筛$[L,R]$。

注意1不是素数，但不会被筛掉，需要特殊处理(巨坑~~)

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const ll N=1e5+10,inf=0x3f3f3f3f;
 6 ll L,R,isp1[N],isp2[N*10],pri[N*10],npri;
 7 void getpri1() {
 8     for(ll i=2; i<N; ++i)isp1[i]=1;
 9     for(ll i=2; i<N; ++i)if(isp1[i])for(ll j=2; i*j<N; ++j)isp1[i*j]=0;
10 }
11 void getpri2() {
12     for(ll i=0; i<=R-L; ++i)isp2[i]=1;
13     for(ll i=2; i*i<=R; ++i)if(isp1[i])
14             for(ll j=max(2ll,(L-1)/i+1); i*j<=R; ++j)isp2[i*j-L]=0;
15 }
16 int main() {
17     getpri1();
18     while(scanf("%lld%lld",&L,&R)==2) {
19         getpri2();
20         npri=0;
21         for(ll i=L; i<=R; ++i)if(isp2[i-L]&&i!=1)pri[npri++]=i;
22         if(npri<2)puts("There are no adjacent primes.");
23         else {
24             ll mi=1,mx=1;
25             for(ll i=2; i<npri; ++i) {
26                 if(pri[i]-pri[i-1]<pri[mi]-pri[mi-1])mi=i;
27                 if(pri[i]-pri[i-1]>pri[mx]-pri[mx-1])mx=i;
28             }
29             printf("%lld,%lld are closest, %lld,%lld are most distant.
",pri[mi-1],pri[mi],pri[mx-1],pri[mx]);
30         }
31     }
32     return 0;
33 }