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;
}