题目描述
tyx最近沉迷于数学，并且他突然对素数产生了奇妙的兴趣
凑巧的是，tyx手里有(n)个数字(x_1,x_2,...,x_n)。
tyx看着手里的一堆不知道从哪里的数字，突然很好奇，他如果从中选出若干个数相加，能有多少种取数的方案，使得得到的和为一个素数？
当然，由于tyx有强迫症，他不仅希望知道满足条件的方案数，也想知道他总共可以得到多少个不同的素数。
遗憾的是，tyx的脑子因为被寒域爷灌了一罐肥宅快乐水，现在似乎不怎么好使，因此他抱住了你的大腿希望你可以帮助他解决。
输入格式
第一行一个整数(n)，表示tyx手里的数的个数。
第二行(n)个整数，表示(x_1,x_2,...,x_n)。
输出格式
第一行一个整数(x)，表示满足和为素数的取数方案数。
第二行一个整数(y)，表示tyx总共可以得到多少个不同的素数。
思路
观察数据范围，发现所有数的和不超过4*1e7，所以空间是允许筛素数法的。
开个大数组，用欧拉筛标记每个数是否为素数，再选数就OK了。
小技巧:集合中任意选元素时我们一般不用dfs，而是用一个数的二进制形式表示选取情况，第i位为1表示选了第i个元素，避免了递归，常数会更小（也许吧）。
代码
#include <cstdlib>
#define maxn (int)(4 * 1e7 + 2)
int book[maxn], p[maxn], a[21], cnt = 0, vis[maxn];
int main() {
int n, i, j, tot = 0, ans1 = 0, ans2 = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
tot += a[i];
}
book[1] = 1;
for (i = 2; i <= tot; i++) {
if (!book[i])
p[++cnt] = i;
for (j = 1; j <= cnt && i * p[j] <= tot; j++) {
book[i * p[j]] = 1;
if (!(i % p[j]))
break;
}
}
for (i = 1; i < (1 << n); i++) {
int sum = 0;
for (j = 1; j <= n; j++)
if ((1 << j - 1) & i)
sum += a[j];
if (!book[sum]) {
ans1++;
if (!vis[sum]) {
ans2++;
vis[sum] = 1;
}
}
}
printf("%d
%d", ans1, ans2);
return 0;
}