【问题描述】
定义两个素数是连续的当且仅当这两个素数之间不存在其他的素数（如 7,11 ,(23,29)。给定N,K，在不超过N的正整数中求能够分解为K个连续的素数的和的最大的那个是多少。
【输入格式】
第一行一个正整数T代表数据组数。
接下来T行每行两个正整数N,K代表一组询问。
【输出格式】
输出共T行，每行一个整数代表答案；如果找不到这样的数，输出−1。
【样例输入】
3
20 2
20 3
20 4
【样例输出】
18
15
17
【样例解释】
╭︿︿︿╮
{/ o o /}
( (oo) )
︶︶︶
【数据规模与约定】
对于20%的数据，1≤N≤100。
对于40%的数据，T=1。
对于60%的数据，所有的询问的N相等。
对于100%的数据，1≤T<2000,1≤N≤106。
一开始肯定是先预处理出所有小于1e6的质数，筛法O(nloglogn)。
由于是2000组数据，1秒钟要算出，所以考虑二分。
预处理先算出素数的前缀和。每次找的时候二分找结束位置，则和为sum[x]-sum[x-k]。
二分的时候要搞清楚末状态，不然很容易错。
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int maxn=1e6+5;
8 int prime[maxn];
9 int vis[maxn];
10 int q[maxn];
11 long long sumx[maxn];
12 int T;long long k,n;int temp=0;
13 long long read()
14 {
15 char c=getchar();long long an=0;
16 while(c<'0'||c>'9')c=getchar();
17 while(c>='0'&&c<='9')
18 {
19 an=an*10+c-'0';
20 c=getchar();
21 }
22 return an;
23 }
24 void solve2()
25 {
26 scanf("%d",&T);
27 for(int qw=1;qw<=T;qw++)
28 {
29 //memset(q,0,sizeof(q));
30 int temp1=0;
31 n=read();k=read();//scanf("%I64d%d",&n,&k);
32 int left=k,right=temp;
33 while(left<=right)
34 {
35 int mid=(left+right)>>1;
36 if(sumx[mid]-sumx[mid-k]<n)
37 left=mid+1;
38 else right=mid-1;
39 }
40 if(sumx[right+1]-sumx[right-k+1]<=n)right++;
41 if(right==k-1)printf("-1
");
42 else printf("%d
",sumx[right]-sumx[right-k]);
43 }
44 return ;
45 }
46 int main()
47 {
48 freopen("dun.in","r",stdin);
49 freopen("dun.out","w",stdout);
50 memset(vis,false,sizeof(vis));
51 for(long long i=2;i<=1000000;i++)
52 {
53 int qw=int(i);
54 if(vis[qw]==true)continue;
55 else
56 {
57 prime[++temp]=qw;
58 if(qw*qw>1e6)continue;
59 for(long long j=i;j*i<=1000000;j++)
60 {
61 if(j*i>1000000)break;
62 int k=int(j*i);
63 vis[k]=true;
64 }
65 }
66 }
67 for(int i=1;i<=temp;i++)
68 {
69 sumx[i]=prime[i];
70 sumx[i]+=sumx[i-1];
71 }
72 solve2();
73 }