首页 > 代码库 > 2002选数
2002选数
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
屏幕输出，格式为：
一个整数（满足条件的种数）。
4 3
3 7 12 19
1
（1<=n<=20，k＜n）
（1<=xi<=5000000）
题解：
搜索+素数。
递归搜索每一个数：两种可能（选、不选），选就在和里面加上去，不选就跳过。最后会求出一些和，判断这些和是不是素数就行了。
var n,m,i,ans:longint;
a:array[0..21]of longint;
procedure dfs(k,s,sum:longint);
var i:longint;
begin
if s=m then
begin
for i:=2 to trunc(sqrt(sum)) do
if sum mod i=0 then exit;
inc(ans);
exit;
end;
if k=n+1 then exit;
dfs(k+1,s+1,sum+a[k]);
dfs(k+1,s,sum);
end;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
dfs(1,0,0);
write(ans);
end.
2002选数