#include <bits/stdc++.h>
using namespace std;
int n, ans, a[15], c[15];
bool p[3000005], used[15];
void dfsm(int now, int sum)
{
    if (p[sum])
        ans++;
    if (now > n)
        return;
    for (int i = 1; i <= n; i++)
        if (!used[i])
        {
            used[i] = true;
            c[now] = a[i];
            dfs(now + 1, sum + a[i] * now);
            used[i] = false;
        }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(p, true, sizeof(p));
    p[0] = p[1] = false;
    for (int i = 2; i <= 3000000; i++)
        if (p[i])
            for (int j = i * 2; j <= 3000000; j += i)
                p[j] = false;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ans = 0;
    dfs(1, 0);
    cout << ans;
    return 0;
}

$n$ 小于等于 $10$ 的时候，$O(n!)$ 时间复杂度都可以跑的通，因此这题我们可以跑一个全排列统计即可。可以使用 dfs 或 STL 里的 next_premutation 函数。

这里提供一个 dfs 做法的标程。

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[15];
int c[15];
bool used[15];
bool p[3000005];
void dfs(int now, int sum)
{
    if (p[sum])
    {
        /*
        cout << sum << " = ";
        for (int i = 1; i < now; i++)
            cout << " " << i << " * " << c[i] << " "
                 << "+\n"[i == now - 1];
        */
        ans++;
    }
    if (now > n)
        return;
     全排列模板

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(p, true, sizeof(p));
    p[0] = p[1] = false;
    for (int i = 2; i <= 3000000; i++)
        if (p[i])
            for (int j = i * 2; j <= 3000000; j += i)
                p[j] = false;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ans = 0;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

请注意：不要在 8 月 18 日 10:30 之前发布本题任何形式的题解，否则你的题解可能会被删除！

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。