题解 | #[NOIP2002]选数#

思路：
利用不降原则和dfs枚举m个数的组合，判断是否是素数，用变量统计即可

#include<iostream>
using namespace std;
int n,m,a[25],sum;
bool zs(int x){
    if(x<2) return 0;//小于2的都不是素数
    for(int i=2;i*i<=x;i++)//枚举到x的平方根
        if(x%i==0) return 0;
    return 1;
}
void dfs(int k,int num,int x){
    if(k>m){//选完m个数后
        if(zs(num)) sum++;//判断是否为素数
        return;
    }
    for(int i=x;i<=n;i++) dfs(k+1,num+a[i],i+1);//不降原则
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1,0,1);
    cout<<sum;
    return 0;
}