3998 - Prime k-tuple

{p₁,..., p_k : p₁ < p₂ <...< p_k} is called a prime k -tuple of distance s if p₁, p₂,..., p_k are consecutive prime numbers and p_k - p₁ = 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 * 10⁹, k < 10, s < 40) .

Output

For each test case, write in one line the numbers of prime k -tuples of distance s .

Sample Input

1

100 200 4 8

Sample Output

思路：区间筛素数；

数据就是很水，没给定【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

Input

Output

Sample Input

Sample Output

最新文章

热门文章