第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-619 选数

#include <stdio.h>
#include <math.h>
int a[25];
int n,k,count;
int panduan(int n)
{
    int i;
    if (n==1)
    return 0;
    int k=(int)sqrt(n);
    for (i=2;i<=k;i++)
        if (n%i==0)
        return 0;
        return 1;
 
}
int DFS(int a[25],int num,int sum,int l)
{
    int i;
    if (num==k)
    {
       if (panduan(sum))
           count++;
    }
    else
    {
       for (i=l;i<n;i++)
        DFS(a,num+1,sum+a[i],i+1);
    }
}
 int main()
 {
     int i,j;
     scanf("%d%d",&n,&k);
     for (i=0;i<n;i++)
      scanf("%d",&a[i]);
      DFS(a,0,0,0);
      printf("%d\n",count);
      return 0;
 }

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 505, mod = 1e9 + 7, INF = 0x3f3f3f3f;
const double eps = 1e-6;

int a[N], sum, n, m, ans;

bool check(int x)
{
	for (int i = 2; i <= x / i; i++)
	{
		if (x % i == 0) return 0;
	}
	return 1;
}

void dfs(int x, int p)
{
	if (x == m + 1)
	{
		if (check(sum))
		{
			ans++;	
		}
		return;
	}
	for (int i = p; i <= n; i++)
	{
		sum += a[i];
		dfs(x + 1, i + 1);
		sum -= a[i];
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	dfs(1, 1);
	cout << ans << endl;
	
	return 0;
}

import java.util.Scanner;

public class Main {
	static int[] a;
	static int[] b;
	static boolean[] vir;
	static int m;
	static int count;

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		m=sc.nextInt();
	    a=new int[n];
	    b=new int[m];
	    vir=new boolean[n];
	    for(int i=0;i<n;i++) {
	    	a[i]=scan.nextInt();
	    }
	    dfs(0,n,0);
	    System.out.println(count);
	    
	}

	public static void dfs(int s, int t, int x) {
		if (s == m) {
			int sum=0;
			
			for(int i=0;i<m;i++) {
				sum+=b[i];
				
			}
			if(f(sum)) {
				 count++;
				}
			return;
		}

		for (int i = x; i < t; i++) {
			if (vir[i] == false) {
				vir[i] = true;
				b[s] = a[i];
				dfs(s + 1, t, i + 1);
				vir[i] = false;

			}
		}
	}
public static boolean f(int a) {
	for(int i=2;i<=a-1;i++) {
		if(a%i==0) {
			return false;
		}
	}
	return true;
}
}

from math import *
from itertools import *

def isprime(n):
    if n==1: return False
    m = int(isqrt(n))+1
    for i in range(2, m):
        if n%i ==0:  return False
    return True

n,k = map(int,input().split())
s = list(map(int,input().split()))
cnt = 0
for e in combinations(s, k):            #所有组合
    num = int(sum(e))                   #求和
    if isprime(num) == True:  cnt+=1
print(cnt)