poj2689Prime Distance 素数测试

朴素素数测试是O(x^1/2)的，每一个数都测试下来就炸了

然而如果全部预处理的话才是做大死，时间空间各种炸（大约有1亿个数）

所以怎么平衡一下呢？

其实在预处理的时候可以只处理一半：把2147483647^1/2内的质数全部预处理出来（这些就是要用的全部质数），然后用这些质数线性筛一筛就能得到正解

= =

没了？

没了。

还是要吐槽一下数论题目虽然代码、题解都很好写，但我不相信我能在赛场上想到正解。。。

 1 #include <cstdio>
 2 #include <iostream>
 3 #define ma 65536 
 4 using namespace std;
 5 bool b[ma];
 6 int a[ma];
 7 bool f[1000001];
 8 int main()
 9 {
10     int l,r,j=0;
11     for(int i=2;i<=ma;i++)
12     {
13         if(!b[i])
14             a[++j]=i;
15         for(int k=1;k<=j && a[k]*i<=ma;k++)
16         {
17             b[a[k]*i]=true;
18             if(i%a[k]==0)
19                 break;
20         }
21     }
22     int n=j;
23     while(~scanf("%d%d",&l,&r))
24     {
25         for(int i=0;i<=r-l;i++)
26             f[i]=true;
27         for(int i=1;i<=n;i++)
28             for(int j=max(2,(l-1)/a[i]+1);j<=r/a[i];j++)
29                 f[a[i]*j-l]=false;
30         int last=-1;
31         int min1=-1,min2,max1=-1,max2;
32         if(l==1)
33             f[0]=false;
34         for(int i=0;i<=r-l;i++)
35         if(f[i])
36         if(last==-1)
37             last=i;
38         else
39         {
40             if(min1==-1)
41             {
42                 min1=last;
43                 min2=i;
44             }
45             if(i-last<min2-min1)
46             {
47                 min1=last;
48                 min2=i;
49             }
50             if(max1==-1)
51             {
52                 max1=last;
53                 max2=i;
54             }
55             if(i-last>max2-max1)
56             {
57                 max1=last;
58                 max2=i;
59             }
60             last=i;
61         }
62         if(max1==-1)
63             printf("There are no adjacent primes.
");
64         else
65             printf("%d,%d are closest, %d,%d are most distant.
",min1+l,min2+l,max1+l,max2+l);
66     }
67     return 0;
68 }

其实压一压行可以在30行左右搞定的