据规模小所以直接深搜即可，省略了判断这个数又没有被选过，省略原因下面解释。

时间复杂度：O(C(n,k)∗S)O(C(n,k)*\sqrt{S})O(C(n,k)∗S ) SSS为kkk个数加起来的maxmaxmax 将质数为偶数的情况排掉，大的数判断能否质因数分解，再使用记忆化来优化，然后加上剪枝和输入优化。(洛谷 hackhackhack 仅用10ms10ms10ms)

根据题意可以得知，从n个数选k个数是组合问题 下面是从第一个数据开始找后面的数 * dg(2,k-1, ...) * dg(3,k-1, ...) * dg(4,k-1, ...) * dg(5,k-1, ...) ......... * dg(n,k-1, ...) * dg(3, k-2, …) * dg(4, k-2, …) * dg(5, k-2, …) * dg(6, k-2, …) ......... * dg(n, k-1, …) AC代码

#include <iostream> using namespace std; int a[20]; int s,k,c = 0, sum = 0; int sushu(int num) { int i; for(i = 2; i<num; i++) { if(num%i==0) break; } if(i == num)return 1; else return 0; } void f(int p,int l) { if(p == k + 1) { c += sushu(sum); return ; } for(int i = l; i <= s; i++) { sum += a[i]; f(p + 1,i + 1); sum -= a[i]; } } int main() { }

据规模小所以直接深搜即可，省略了判断这个数又没有被选过，省略原因下面解释。