题解：UVA10140 Prime Distance

数据范围太大

于是采用一个类似于离散化的操作

首先需要明确一个定理

如果n是一个合数，那么n一定有一个不超过

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 const int N=100010; 
 5 const int X=2147483647;
 6 typedef long long ll; 
 7 using namespace std;
 8 bool vis[N*10];
 9 ll prime[N], k=0;
10 ll prime2[N*10], top=0;
11 void shai(){
12     memset(vis,false,sizeof(vis));
13     k=0;
14     for(ll i=2; i<N; ++i){
15         if(!vis[i])
16             prime[++k]=i;
17         for(int j=i*2; j<N; j+=i)
18             vis[j]=true;
19     }
20 }
21 int main(){
22     shai();
23     ll L, R;
24     while(scanf("%lld%lld", &L, &R)!=EOF){
25         L=max(L, 2ll);
26         top=0;
27         memset(vis, 0, sizeof(vis));
28         for(ll i=1; prime[i]*prime[i]<=R && i<=k; ++i){
29             int s=L/prime[i]+(L%prime[i]>0);
30             if(s==1)    s=2;
31             for(ll j=prime[i]*s; j<=R; j+=prime[i])
32                 vis[j-L]=true;
33         }
34         for(ll i=0; i<=R-L; ++i)
35             if(!vis[i])    prime2[++top]=i+L;
36         ll minn=X, a=0;
37         ll maxn=0, b=0;
38         for(ll i=1; i<top; ++i){
39             if(prime2[i+1]-prime2[i]<minn){
40                 minn=prime2[i+1]-prime2[i];
41                 a=i;
42             }
43             if(prime2[i+1]-prime2[i]>maxn){
44                 maxn=prime2[i+1]-prime2[i];
45                 b=i;
46             }
47         }
48         if(top<2)
49             printf("There are no adjacent primes.
");
50         else
51             printf("%lld,%lld are closest, %lld,%lld are most distant.
", prime2[a], prime2[a + 1], prime2[b], prime2[b + 1]);
52     }
53     return 0;
54 }