A27688. 素数种类（prime）
填空题
中等
知识点
题目描述
素数种类（prime）
题目描述
已知n个整数X1,X2....Xn以及1个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数的共有多少种。
输入格式
第一行两个空格隔开的整数n，k(1<n≤20，k<n)。
第二行n个整数，分别为x 1,x 2,......, x n (1≤x i≤5×106)。
输出格式
输出一个整数，表示种类数。
Samples
输入数据 1
4 3
3 7 12 19
输出数据 1
1
样例1解释
当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，故输出1。
参考答案
#include <iostream>
#include <cstdio>
using namespace std;
int n, k, ans;//ans存储计数结果
int a[25];
//判断素数
bool isprime(int a) {
for (int i = 2; i * i <= a; i++) //判断是否有2-根号a的因数
if (a % i == 0) //如果整除，说明除了1和它本身还有别的因数，即不是素数
return false;
//程序都到这里的话就说明此为素数
return true;
}
//最重要的递归
void dfs(int m, int sum, int startx) {
//m代表现在选择了多少个数
//sum表示当前的和
//startx表示升序排列，以免算重
if (m == k) { //如果选完了的话
if (isprime(sum)) //如果和是素数
ans++; //ans加一
return ;
}
for (int i = startx; i < n; i++)
dfs(m + 1, sum + a[i], i + 1);//递归
//步数要加一，和也要加
//升序起始值要变成i+1,以免算重
return ;//这一个步骤下，所有的都枚举完了
//直接返回去
}
int main() {
scanf("%d%d", &n, &k); //输入
for (int i = 0; i < n; i++)
scanf("%d", &a[i]); //循环读入
dfs(0, 0, 0); //调用函数
printf("%d\n", ans); //输出答案
return 0;
}
上一题
下一题