【题解】选数 搜索 CODEVS – 1008 NOIP2002 普及组

传送门=￣ω￣=

思路：dfs 枚举所有可能，对于可能得数字 P 可以在√P 的复杂度内判断 P 是否为质数，然后就没有然后了。

代码：

#include <iostream>
using namespace std;
int n,k,x[25],ans;
bool judge(int num)
{
    for(int i=2;i*i<=num;i++)if(!(num%i))return 0;
    return 1;
}
void dfs(int c1,int c2,int tot)
{
    if(c2>k){if(judge(tot))ans++;return;}
    for(int i=c1+1;i<=n;i++)dfs(i,c2+1,tot+x[i]); 
} 
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>k;for(int i=1;i<=n;i++)cin>>x[i];
    dfs(0,1,0),cout<<ans;
    return 0;
}