Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

A seemingly violent problem is actually to use the brain

Topic describes

Given NNN integers x1,x2,… xnx_1,x_2,\cdots, X_nx1,x2,… xn, and 111 integers k (k

Now, I want you to figure out how many ways that and are prime.

For example, only one of the sums is prime: 3+7+19=293+7+19=293+7+19=29.

Input format

The first line contains two blank separated integers n,k (1≤n≤20,k

Xn (1≤xi≤5×106) x_1,x_2,\cdots,x_n (1 \le x_i \le 5\times 10^6) x1,x2,… xn (1≤xi≤5×106).

The output format

Output an integer representing the number of types.

Input and output examples

The input

4, 3, 3, 7, 12, 19Copy the code

The output

1
Copy the code

Is it really as easy as it looks?

Everyone at first glance at this problem, will find, for the sample of the problem, directly to 3 for cycle violence traversal is not ok??

However, the k changes. In other words, when k = 4, you do 4 for loops, and when k = 20, you do 20 for loops…

And to tell you the truth, some people do:

if (k==2)  
     {
      for (int i=1; i<=n- 1; i++)for (int i1=i+1; i1<=n; i1++)if (zs(a[i]+a[i1])) s++;/ / calculate
        return; }...if (k==5)  
     {
       for (int i=1; i<=n4 -; i++)for (int i1=i+1; i1<=n- 3; i1++)for (int i2=i1+1; i2<=n2 -; i2++)for (int i3=i2+1; i3<=n- 1; i3++)for (int i4=i3+1; i4<=n; i4++)if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]))s++;
          return; }...Copy the code

When I look at this code, I can only say that the number of lines of code is pretty good for you (and I don’t mean to mock the people who write this code).

Solve the traversal problem without a for loop?

Let’s play one big killer: recursion.

Let’s look at the traversal process:

With KKK subscripts I1… ,iki_1,… ,i_ki1,… Ik represents the selected number.

How to traverse i1,… ,iki_1,… ,i_ki1,… , ik? The usual practice is:

Fixed i1,… ,iki_1,… ,i_ki1,… , so i1I_1I1 through iKI_KIk is always left to right. So the way to traverse is to fix i1i_1i1 in all the available positions, and then i2… ,iki_2,… ,i_ki2,… Ik recursively traverses the interval to the right of i1i_1i1.

For example, in an interval [1,20][1,20][1,20], how to traverse i1… ,i10i_1,… ,i_10i1,… I10? That is, shilling i1i_1i1 is 1, and then making the problem equivalent to how to traverse i2 in the interval [2,20][2,20][2,20]… ,i10i_2,… ,i_10i2,… I10; Let i1i_1i1 be 222, then let the problem be equivalent to how to traverse i2 in the interval [3,20][3,20][3,20] [3,20]… ,i10i_2,… ,i_10i2,… ,i10… When i1i_1i1 is 111111, i2 is traversed in the interval [12,20][12,20][12,20]… ,i10i_2,… ,i_10i2,… I10, so I have the whole traversal.

In this way, we can solve the parent problem through many subproblems, which means we can write recursive functions!

void recur(int i,int remain,int now){
	if(remain==1) {for(; i<=n-remain; i++){//if(! isnot[arr[i]+now])cnt++;
			if(prime(arr[i]+now))cnt++;
		}
		return;
	}
	for(; i<=n-remain; i++){recur(i+1,remain- 1,now+arr[i]);
	}
	return;
}
Copy the code

Where I is the starting point of the traversal interval (mainly n-1), remain is how many subscripts need to be traversed, and now is the sum that has been determined when traversing to this subproblem when the preceding number is fixed.

All the code

#include<iostream>
#include<cmath>
using namespace std;
const int maxn=(int)1e8;
int arr[30];
int isnot[maxn];
int cnt;
int n,k;
int prime(int n){
	if(n==2)return 1;
	for(int i=2; i<=sqrt(n)+1; i++){if(n%i==0)return 0;
	}
	return 1;
}
void recur(int i,int remain,int now){
	if(remain==1) {for(; i<=n-remain; i++){//if(! isnot[arr[i]+now])cnt++;
			if(prime(arr[i]+now))cnt++;
		}
		return;
	}
	for(; i<=n-remain; i++){recur(i+1,remain- 1,now+arr[i]);
	}
	return;
	
}

int main(a){
	
	cin>>n>>k;
	for(int i=0; i<n; i++){ cin>>arr[i]; }recur(0,k,0);
	cout<<cnt;
}
Copy the code