首页 > 代码库 > 3998 - Prime k-tuple
3998 - Prime k-tuple
{p1,..., pk : p1 < p2 <...< pk} is called a prime k -tuple of distance s if p1, p2,..., pk are consecutive prime numbers and pk - p1 = s . For example, with k = 4 , s = 8 , {11, 13, 17, 19} is a prime 4-tuple of distance 8.
Given an interval [a, b] , k , and s , your task is to write a program to find the number of prime k -tuples of distance s in the interval [a, b] .
Input
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data set, there is only one line containing 4 numbers, a , b , k and s (a, b < 2 * 109, k < 10, s < 40) .
Output
For each test case, write in one line the numbers of prime k -tuples of distance s .
Sample Input
1100 200 4 8
Sample Output
2
思路：区间筛素数；
数据就是很水，没给定【a,b】区间的大小，然后筛法水过。然后统计的时候，维护两个端点就行了。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 using namespace std; 8 typedef long long LL; 9 bool prime[100005];10 bool prime_max[20*1000000];11 int ans[100005];12 LL ac[1000007];13 int main(void)14 {15 memset(prime,0,sizeof(prime));16 int i,j;17 int cn = 0;18 for(i = 2; i < 1000; i++)19 if(!prime[i])20 for(j = i; (i*j) < 100005; i++)21 prime[i*j] = true;22 for(i = 2; i < 100005; i++)23 {24 if(!prime[i])25 ans[cn++] = i;26 }27 int n;28 scanf("%d",&n);29 LL a,b,k,t;30 while(n--)31 {32 scanf("%lld %lld %lld %lld",&a,&b,&k,&t);33 memset(prime_max,0,sizeof(prime_max));34 LL s ;35 for(i = 0; i < cn; i++)36 {37 for(s = max(2LL,a/ans[i])*ans[i]; s <= b; s += ans[i])38 {39 if(s >= a)40 prime_max[s-a] = true;41 }42 }43 int v = 0;44 for(s = a; s <= b; s++)45 {46 if(!prime_max[s-a])47 ac[v++] = s;48 }49 int l = 0;50 int r = k-1;51 LL ask = 0;52 while(true)53 {54 if(r >= v)55 break;56 if(ac[r] - ac[l] == t)57 {58 ask++;59 }60 l++;61 r++;62 }63 printf("%lld\n",ask);64 }65 return 0;66 }
3998 - Prime k-tuple