poj 2689 Prime Distance(大区间素数)

题目链接：poj 2689 Prime Distance

题意：

给你一个很大的区间（区间差不超过100w），让你找出这个区间的相邻最大和最小的两对素数

题解：

正向去找这个区间的素数会超时，我们考虑逆向思维：

我们先用线性筛筛出前50000的素数，在int范围内的区间的合数的因子都在我们之前筛出来了，

然后我们就把这个区间的合数标记出来，剩下的就是素数了。

标记合数也是用全部的素数去筛一下，这样就能快速的标记这个区间的合数，然后在暴力枚举一下这个区间，更新一下答案。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define F(i,a,b) for(int i=a;i<=b;++i)
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 const int N=5e4+7;
 9 int primes[N],tot=0;
10 bool vis[N];
11 void Euler(){
12     F(i,2,N-7){
13         if(!vis[i])primes[++tot]=i;
14         F(j,1,tot){
15             if(i*primes[j]>N)break;
16             vis[i*primes[j]]=1;
17             if(i%primes[j]==0)break;
18         }
19     }
20 }
21 
22 int L,U;
23 int a[N*20],ed;
24 
25 int main()
26 {
27     Euler();
28     while(~scanf("%d%d",&L,&U))
29     {
30         if(L==1)L=2;//特别注意
31         int en=U-L;
32         F(i,0,en)a[i]=0;
33         F(i,1,tot)
34         {
35             int l=(L-1)/primes[i]+1,r=U/primes[i];
36             F(j,l,r)if(j>1)a[j*primes[i]-L]=1;
37         }
38         int an1,dis1=100*N,an2,dis2=-1,pre=-1;
39         F(i,0,en)
40         {
41             if(!a[i])
42             {
43                 if(pre!=-1)
44                 {
45                     if(i-pre<dis1)dis1=i-pre,an1=pre;
46                     if(i-pre>dis2)dis2=i-pre,an2=pre;
47                 }
48                 pre=i;
49             }
50         }
51         if(dis2==-1)puts("There are no adjacent primes.");
52         else printf("%lld,%lld are closest, %lld,%lld are most distant.
",(ll)an1+L,(ll)an1+L+dis1,(ll)an2+L,(ll)an2+L+dis2);
53     }
54     return 0;
55 }

View Code