选数

问题描述

已知n个整数 $x_1,x_2,…,x_n$ 和1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当$n=4,k=3,x_1=3,x_2=7,x_3=12,x_4=19$时，可得全部的组合与它们的和为：

$3+7+12=22$
$3+7+19=29$
$7+12+19=38$
$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

输入包含两行
第一行两个数n,k
第二行n个数依次表示$x_i$

输出格式

一个整数，表示合法的组合数

样例输入

4 3
3 7 12 19

样例输出

1

数据规模和约定

1<=k<n<=20
1<=$x_i$<=5000000

提示

素数的判定方法

bool prime(int n)
{
        if（n==1) return false;
        if (n==2) return true;
	for(int i=2;i*i<=n;i++)
	   if (n%i==0) return false;
	return true; 
}

#include <bits/stdc++.h>
using namespace std;

int ans = 0;
int x[25];

bool isPrime(const int& n) {
    if (n == 1) return false;
    if (n == 2) return true;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

void dfs(const int& a, const int& b, const int& k, const int& sum, int step) {
    if (step == k) {
        if (isPrime(sum))
            ++ans;
        return;
    }
    ++step;
    for (int i = a; i < b; ++i) {
        dfs(i + 1, b, k, sum + x[i], step);
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n;++i)
        scanf("%d ", &x[i]);
    dfs(0, n, k, 0, 0);
    cout << ans;
    return 0;
}