这道题数据量不大,最大18W左右,回溯即可.

#include <stdio.h>
#include <stdlib.h>

long x[21];
long a[21];
long sum;
int n,k;

int main()
{
    int i;
    input();
    for(i=1;i<=n;i++)
        dp(i,1);    
    output();    
    return(0);
}    

int input()
{
    int i;
    FILE *fp;
    fp=fopen("choose.in","r");
    fscanf(fp,"%d",&n);
    fscanf(fp,"%d",&k);
    for(i=1;i<=n;i++)
        fscanf(fp,"%ld",&x[i]);
    fclose(fp);
}

int dp(int pos,int p)
{
    int i;    
    a[p]=pos;        
    if(p==k)
        add();
    else
        for(i=pos+1;i<=n;i++)
             dp(i,p+1);     
}

int pd(long xx)
{
    int i;
    for(i=2;i*i<=xx;i++)
        if(xx%i==0)
            return(0);
    return(1);        
}        

int add()
{
    int i;
    long s=0;
    for(i=1;i<=k;i++)
        s+=x[a[i]];
    if(pd(s)==1)
        sum++;   
}  

int output()
{
    FILE *fp;
    fp=fopen("choose.out","w");
    fprintf(fp,"%ld",sum);
    fclose(fp);
}