#include<bits/stdc++.h>
using namespace std;
int n;
int a[25];
int ans;
bool is_prime(int x)
{
    if (x < 2)
        return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
int dis[10];//dis[i]:第i个数选择ans[i] 
bool vis[10];//vis[i]:a[i]有没有被选过 
bool check(int nn){
	int X=0;
	for(int i=1;i<=nn;i++)
		X+=i*dis[i];
	return is_prime(X);
}
//当前考虑选谁作为第step个数
void dfs(int step){
	//之前已经选了step-1个数
	if(check(step-1))
		ans++;
	if(step==n+1)
		return;
	//考虑第step个数选谁？
	for(int i=1;i<=n;i++){
		if(!vis[i])
		{
			//记录 
			vis[i]=true;
			dis[step]=a[i];
			//做下一步 
			dfs(step+1);
			//取消记录 
			vis[i]=false;
			dis[step]=0; 
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	ans=0;
	dfs(1);
	cout<<ans<<"\n";
	return 0;
}

25ms筛法

值得注意： 筛法数组至少开到2250000（=(1+9)*9/2*5e4) ）

#include<bits/stdc++.h>
using namespace std;
bool su[9000005],chosen[10];
int n,cnt=0;
int a[10];
int ans[40];
void dfs(int now,int he)
{
    if(su[he])
    {
        /*              //去掉注释 输出每组解释
        cout<<he<<" = ";
        for(int i=1;i<=now-1;i++)
        {
            if(i!=1)cout<<" +";
            cout<<" "<<i<<" * "<<ans[i];
        }
        cout<<endl;
        */
       cnt++;
    }
    if(now>n)return;
    for(int i=1;i<=n;i++)
    {
        if(chosen[i]==0)
        {
            chosen[i]=1;
            ans[now]=a[i];
            dfs(now+1,he+a[i]*now);//记录和更方便判定质数
            chosen[i]=0;
        }
    }
}

int main()
{
    memset(su,1,sizeof(su));//筛法
    su[0]=su[1]=0;
    for(int i=2;i<2250005;i++)
    {
        if(su[i]==0)continue;
        for(int j=2*i;j<2250005;j+=i)
            su[j]=0;
    }

    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,0);
    cout<<cnt;
    return 0;
}

再组合质数

基本代码和上一题组合质数相差无几，唯一需要考虑的是本题的每一层深搜都需要从1-n，故需要查重数组进行查重，如果没有使用过再使用。

可以写埃氏筛法，但是质数判断也可以直接写最简单、复杂度最高的，时间绰绰有余。

#include<bits/stdc++.h>
using namespace std;
int n,a[30],num;
bool use[50010];   //判断数组
bool zhishu(int x)  //质数判断
{
	if(x==0||x==1) return false;
	for(int i1=2;i1*i1<=x;i1++)
		if(x%i1==0)
			return false;
	return true;
}
void dfs(int m,int sum)   //深搜(第几层，当前总和为多少）
{
	if(m>n+1) return;    //如果递归过深就直接返回
	if(zhishu(sum)==true)
	{
		num++;
		//cout<<'\n';
	}    //如果当前加和为质数就总数+1
	for(int i=1;i<=n;i++)
	{
		if(use[i]==false)  //如果当前数字没有被使用
		{
			use[i]=true;  //标记被使用
			sum+=m*a[i];  //乘m然后加
			//cout<<m<<" a[i]:"<<a[i]<<" sum"<<sum<<'\n';  //调试用代码，请忽略
			dfs(m+1,sum);  //调用下一层
			sum-=m*a[i];  //回溯
			use[i]=false;
		}
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1,0);
	cout<<num;
	return 0;
}