LA 3998 Prime k-tuple

题意：如果K个相邻素数p1,p2,p3.....pk满足pk-p1=s，称这些素数组成一个距离为s的素数K元组，输入a,b,k,s，输出区间[a,b]内距离为s的素数k元组的个数。

思路：先打到50000素数表，然后暴力求出a,b区间的素数，然后判断。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int t;
 7 int a,b,k,s,cnt;
 8 bool vis[500000];
 9 int f[500000];
10 int p[10000000];
11 void getprime()
12 {
13     cnt=0;
14     memset(vis,0,sizeof(vis));
15     vis[1]=true;
16     vis[0]=true;
17     for(int i=2; i<=50000; i++)
18     {
19         if(!vis[i])
20         {
21             f[cnt++]=i;
22             for(int j=i*2; j<=50000; j+=i)
23             {
24                 vis[j]=true;
25             }
26         }
27     }
28 }
29 
30 int main()
31 {
32     getprime();
33     scanf("%d
",&t);
34     while(t--)
35     {
36         scanf("%d%d%d%d",&a,&b,&k,&s);
37         memset(p,0,sizeof(p));
38         int ans=0;
39         int t1=0;
40         for(int i=a; i<=b; i++)
41         {
42             if(i<=50000)
43             {
44                 if(!vis[i]) p[t1++]=i;
45             }
46             else
47             {
48                 bool flag=true;
49                for(int j=0; j<cnt&&f[j]*f[j]<=i; j++)
50                {
51                     if(i%f[j]==0)
52                     {
53                         flag=false;
54                         break;
55                     }
56                }
57                if(flag)
58                {
59                    p[t1++]=i;
60                }
61             }
62         }
63         for(int i=0; i<t1; i++)
64         {
65             if(p[i+k-1]-p[i]==s)
66             {
67                 ans++;
68             }
69         }
70         printf("%d
",ans);
71     }
72     return 0;
73 }

View Code