递归---选数

选数

选数

题意

给定n,k,从 n 个整数中任选 k 个整数相加,如果相加的和为素数就记一次，输出有几个和为素数

思路

本题使用递归，先算出K个数的和，再判断是否为素数，如果是素数就记一，最后输出

算法一：递归

时间复杂度

普及

实现步骤

定义一个递归函数dfs，如果K个数的和为素数记一，并继续递归，防止算重。定义bool值判断是否为素数

代码

#include <iostream>
#include <cstdio>
using namespace std;
bool isprime(int a){//判断素数
    for(int i = 2;i * i <= a; i++)
        if(a % i == 0)
            return false;//扔回false
    return true;//扔回true
}

int n,k;
int a[25];
long long ans;

void dfs(int m, int sum, int startx){//递归
//m代表现在选择了多少个数
//sum表示当前的和
//startx表示升序排列，以免算重
    if(m == k){//如果全部选完 
        if(isprime(sum))//如果和为素数
            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);//调用函数，定义最初值为0 
    printf("%d\n",ans); 
    return 0;
}