HDU 3823 Prime Friend (打表+线性筛)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector> 
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define MAXN int(2e7)  //设定这个范围需要先将素数打表看一下，满足相邻素数差值<=150的最大素数是多少
 8 #define N int(2e6)     //本题这里的范围卡得很严
 9 typedef long long ll;
10 int prime[N],cnt;
11 bool isprime[MAXN+100];
12 vector<int>vec[155];
13 
14 void GetPrime(){   //线性筛O(n)得到素数
15     cnt=0;memset(isprime,false,sizeof(isprime));
16     for(int i=2;i<MAXN;i++){
17         if(!isprime[i])prime[++cnt]=i;
18         for(int j=1;j<=cnt && (ll)i*prime[j] < MAXN;j++){
19             isprime[i*prime[j]] = true;
20             if(i%prime[j]==0)break;
21         }
22     }
23 }
24 void init(){
25     GetPrime();
26     for(int i=0;i<=150;i++)vec[i].clear();
27     for(int i=1;i<cnt;i++){    //记录所有满足差值为tmp的素数值
28         int tmp=prime[i+1]-prime[i];
29         if(tmp<150)vec[tmp].push_back(prime[i]);
30     }
31 }
32 
33 int main(){
34     init();
35     int T,ncase=0;scanf("%d",&T);while(T--){
36         int a,b;scanf("%d%d",&a,&b);
37         if(a<b)swap(a,b);
38         int tmp=a-b,ans=-1;    //得到a、b的差值
39         for(int i=0;i<vec[tmp].size();i++){
40             if(vec[tmp][i]>=b){
41                 ans=vec[tmp][i]-b;
42                 break;
43             }
44         }
45         printf("Case %d: %d\n", ++ncase, ans);
46     }
47 }