素数区间筛法

题目链接：https://cn.vjudge.net/contest/319720#overview

题目大意：输入两个数L和U(1<=L<U<=2 147 483 647)，要找出两个相邻素数C1和C2(L<=C1<C2<=U)是距离最小的，如果相邻素数不止一对，选择最初的，还要找出两个相邻的素数D1，和D2是距离最大的（同样在有多对的情况下选择最初的）

其中L<U，L和U的差不超过1 000 000

输入样例：

2 17
14 17

输出样例：

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

思路：

需要求出给定范围内区间所有的素数，然后再把素数间的最大距离、最小距离求出来。所以我们首先得用筛法筛出区间[L,U]范围内的素数。

因为数据区间超过的上界打到21亿，不能将所有小于21亿的素数存下来，不过我们发现区间的长度不超过1 000 000，使用筛法筛掉[L,U]区间的所有非素数，需要知道[L,U]区间的所有非素数的素数因子（因为一个非素数是被它最小的素因子筛掉）。2147483647内的数或者是素数，能被根号2147483647内的素数整除，也就是说，[L,U]区间的所有非素数的素数因子都在根号2147483647内。

可以预先将根号2147483647内的所有素数找出来，然后用这些素数去筛掉指定区间的所有非素数

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const int maxn=50005;
 9 int prime[maxn];
10 int l,u,tot=0;
11 bool isprime[1000005];
12 void getprime(int N){
13     memset(prime,0,sizeof(prime));
14     for(int i=2;i<=N;i++){
15         if(!prime[i])
16             prime[tot++]=i;
17         for(int j=0;j<tot&&prime[j]*i<=N;j++){
18             prime[i*prime[j]]=1;
19             if(i%prime[j]==0) break;
20         }
21     }
22 }
23 int main(){
24     //freopen("../in.txt","r",stdin);
25     getprime(50002);
26     while(cin>>l>>u){
27         memset(isprime,true,sizeof(isprime));
28         for(int i=0;i<tot;i++){
29             int a=(l-1)/prime[i]+1,b=u/prime[i]; // l和r表示了当前范围里的数对这个素数的最小倍数和最大倍数。 为什么这样写，可以自己举例来理解
30             for(int j=a;j<=b;j++) if (j>1) isprime[j*prime[i]-l]=0; // 当j=1 的时候这个时候就是prime[i]，prime[i]就是素数
31         }
32         if(l==1) isprime[0]=0; //注意特判l=1的情况
33         int pos=-1,l1,r1,l2,r2,maxdis=0,mindis=0x3f3f3f3f;
34         for(int i=0;i<=u-l;i++){
35             if(isprime[i]){
36                 if(pos==-1) {
37                     pos=i;
38                     continue;
39                 }
40                 if(i-pos<mindis){
41                     l1=l+pos;
42                     r1=l+i;
43                     mindis=i-pos;
44                 }
45                 if(i-pos>maxdis){
46                     maxdis=i-pos;
47                     l2=l+pos;
48                     r2=l+i;
49                 }
50                 pos=i;
51             }
52         }
53         if(maxdis==0) printf("There are no adjacent primes.\n");
54         else printf("%d,%d are closest, %d,%d are most distant.\n",l1,r1,l2,r2);
55     }
56     return 0;
57 }