P1036 [NOIP2002 普及组] 选数 (判断素数，dfs）

下为代码

主要涉及到判断素数和dfs两个知识点

判断素数的模板

int isprime(int n)
{
	if(n <= 1) return 0;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0) return 0;
	}
	return 1;
}

dfs

重点理解这里的dfs，借助样例理解。

void dfs(int dep,int k1,int sum){//depth深度初始为1
	//以样例为例子，我们要拿三个数的和，k1用来判断是否到达3
	//sum是这三个数的和，初始为0
	if(dep == n + 1)//到达最深处的下一个就判断一次
	{
		if(k1 != k) return;
		//加的数不到三个则返回到上一次dfs
		if(isprime(sum)) ans++;
		return;
	}
	dfs(dep+1,k1+1,sum+x[dep]);
	//若选了这数，则将它加上，深度加一，选的数的数目加一
	dfs(dep+1,k1,sum);
	//若没选这个数，就不加，深度加一，选的数的数目不变
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int x[30];
int n,k;
int ans = 0;

int isprime(int n)
{
	if(n <= 1) return 0;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0) return 0;
	}
	return 1;
}

void dfs(int dep,int k1,int sum){//depth深度初始为1
	//以样例为例子，我们要拿三个数的和，k1用来判断是否到达3
	//sum是这三个数的和，初始为0
	if(dep == n + 1)//到达最深处的下一个就判断一次
	{
		if(k1 != k) return;
		//加的数不到三个则返回到上一次dfs
		if(isprime(sum)) ans++;
		return;
	}
	dfs(dep+1,k1+1,sum+x[dep]);
	//若选了这数，则将它加上，深度加一，选的数的数目加一
	dfs(dep+1,k1,sum);
	//若没选这个数，就不加，深度加一，选的数的数目不变
}

int main(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> x[i];
	dfs(1,0,0);//从一开始深度搜索
	cout << ans << '\n';
	return 0;
}