题解(小时间复杂度)

#include <bits/stdc++.h>
using namespace std;
int a,k,n[50],ant=0,m[50],s[500005],t=0,ans=0;
void dfs(int x,int y){
	if(x>k){
		if(!s[ant])ans++;
		return;
	}
	for(int i=y+1;i<=a;i++){
		if(m[i])continue;
		m[i]=1;
		ant+=n[i];
		dfs(x+1,i);
		m[i]=0;
		ant-=n[i];
	}
}
void ss(){
	s[0]=1;
	s[1]=1;
	for(int i=2;i<=t;i++){
		if(s[i])continue;
		for(int j=i;j<=t/i+1;j++){
			s[i*j]=1;
		}
	}
}
bool cmp(int x,int y){
	return x>y;
}
int main(){
	cin>>a>>k;
	for(int i=1;i<=a;i++){
		cin>>n[i];
	}
	sort(n+1,n+a+1,cmp);
	for(int i=1;i<=k;i++)t+=n[i];
	ss();
	dfs(1,0);
	cout<<ans;
}