已知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
7 12 19
输出：
  1
源程序：
#include<iostream>
#include<math.h>
  const int N=21;
  using namespace std;
  int issushu(long num)
  {
      for(long i=2;i<=sqrt(num);i++)
      if(num%i==0)
          return 0;
      return 1;
  }
long totalsum(long a[],int n)
{
    long sum=0;
    for(int i=0;i<n;i++)
      sum+=a[i];
    return sum;
}
int main()
{
    cout<<endl<<"please input the number(0~20) of the numlist and the choose numbers:";
    int num=0,k=0;
    cin>>num>>k;
    cout<<"please input "<<num<<" listnum:";
    long num1[N],num2[N];
    for(int i=0;i<num;i++)
        cin>>num1[i];
    long num3=0,count=0;
    for(int j=0;j<k;j++)
       num2[j]=num1[j];
    num3=totalsum(num2,k);
    if(issushu(num3))
    count++;
    int m=0;
    long data=0;
    for(int n=0;n<k;n++)
    {
        data=num2[n];
      for(m=k;m<num;m++)
      {
          num2[n]=num1[m];
          num3=totalsum(num2,k);
          if(issushu(num3))
              count++;
      }
      num2[n]=data;
    }
    cout<<endl<<"the kinds number is:"<<count<<endl;
    return 0;
}

评论