洛谷------P1036 [NOIP2002 普及组] 选数

#include<iostream>
using namespace std;
#include<bits/stdc++.h>
class Solution {
	vector<int> num;
	int sum = 0;
	//判断一个数是否为质数
	bool isPrime(int num)
	{
		if (num <= 3) {
			return num > 1;
		}
		// 不在6的倍数两侧的一定不是质数
		if (num % 6 != 1 && num % 6 != 5) {
			return false;
		}
		int Sqrt =sqrt(num);
		for (int i = 5; i <= Sqrt; i += 6) {
			if (num % i == 0 || num % (i + 2) == 0) {
				return false;
			}
		}
		return true;
	}
public:
	int solution(vector<int>& v,int k,int index)
	{
		if (k==0)
			return  isPrime(accumulate(num.begin(), num.end(), 0))?++sum:sum;
		int nums = k - num.size();//剩余需要选择的数字个数
		int selNum = v.size() - index-1;//当前剩余最多可选的数字个数
		for (int i = index; i < v.size()&&selNum>=nums; i++)
		{
			num.push_back(v[i]);
			solution(v, k-1, i + 1);
			num.pop_back();
		}
		return sum;
	}
};
int main()
{
	Solution s;
	vector<int> v;
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int val;
		cin >> val;
		v.push_back(val);
	}
	cout << s.solution(v, k, 0) << endl;
	return 0;
}