专题1—D - 加法大湿

#include <stdio.h>
#define N 21
int arr[N];
int ans;
int n, k;
int prime(int n);
void dfs(int sum, int cnt, int flag);
void dfs(int sum, int cnt, int flag) //总和、个数、标记
{
    if (k == cnt)
    {
        if (prime(sum))
        {
            ans++;
        }
        return;
    }
    for (int i = flag; i <= n; i++)
    {
        dfs(sum + arr[i], cnt + 1, i + 1);
    }
}
int prime(int n)
{
    if (n == 1)
    {
        return 0;
    }
    for (int i = 2; i < n; i++)
    {
        if (!(n % i))
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int i;
    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dfs(0, 0, 1);
    printf("%d\n", ans);
    return 0;
}