洛谷oj---1036 选数

题目：https://www.luogu.org/problemnew/show/P1036

简单的dfs，这类题目要引起重视。

bool isPrime(int num){ //判断是否是质数
if(num==1) return false;
for(int i=2;i<=(int)sqrt(num);i++){
if(num%i==0) return false;
}
return true;
}

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int a[30];
bool isPrime(int num){
 if(num==1) return false;
 for(int i=2;i<=(int)sqrt(num);i++){
  if(num%i==0) return false;
 }
 return true;
}
void dfs(int k,int sum,int start,int end,int &count){
 if(k==0){
  if(isPrime(sum)) count++;
  return;
 }
 for(int i=start;i<end;i++){
  dfs(k-1,sum+a[i],i+1,end,count);
 }
}
int main(){
 int n,k;
 scanf("%d%d",&n,&k);
 for(int i=0;i<n;i++){
  scanf("%d",a+i);
 }
 int count=0;
 dfs(k,0,0,n,count);
 printf("%d",count);
}