【递归入门】组合+判断素数

雨点打透心脏的1/2处 2023-02-12 11:23 21阅读 0赞

## 【递归入门】组合+判断素数 ##

题目描述

已知 n 个整数b1,b2,…,bn以及一个整数 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） 
    第二行n个整数：x1,x2，…,xn （1<=xi<=5000000）

输出

一个整数（满足条件的方案数）。

样例输入

4 3
    3 7 12 19

样例输出

#include <cstdio>
    #include <cmath>
    const int maxn = 25;
    int n,k,A[maxn];
    int count = 0;
    
    //判断sum是否为素数 
    bool prime(long long sum){
        
     int i;
     if(sum <= 1) return false; 
     int sqr = (int)sqrt(1.0 * sum); //取sum的平方根 
     for(i = 2; i <= sqr; i++){
          
     //若n%k == 0，k*(n/k) == 0,则k和n/k一定满足一个大于sqrt(sum),一个小于sqrt(sum) 
      if(sum % i == 0){
        
       return false;
      }//if
     }//for
     return true;
    }
    
    //在n个数中选择k个数 
    void choose(int index,int num,long long sum){
        
    //index表示待选择数组的坐标，num表示已经选择的个数，sum表示已选择的数之和 
     if(num == k){
         //已选择k个数 
      if(prime(sum)){
          
       count++;  //是素数 
      }
      return;
     } 
     if(index == n) return; 
     choose(index + 1, num + 1, sum + A[index]);
     choose(index + 1, num, sum);
    }
    
    int main(){
        
     int i;
     scanf("%d%d",&n,&k);
     for(i = 0; i < n; i++){
        
      scanf("%d",&A[i]);
     }
     choose(0,0,0);
     printf("%d\n",count);
    }