//判断质数
static boolean isPrime(int num){
if (num == 0||num==1)
return false;
if (num == 2 || num == 3)
return true;
if (num % 6 != 1 && num % 6 != 5)
return false;
int end = (int) Math.pow(num,1.0/2 );
for (int i = 5;
i <= end;
i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
static void rcs(List sum,List list,int k,int idx,int[] arr){
if(list.size()==k+1){
sum.add(list.get(0));
//加入k个数后,将和加入sum
}else {
//从idx开始为本层所能取的数,遍历添加
for (int i = idx;
i < arr.length;
i++) {
list.add(arr[i]);
list.set(0,list.get(0)+arr[i]);
//修改组合的和
rcs(sum,list,k,i+1,arr);
list.set(0,list.get(0)-arr[i]);
//还原初始状态,再添加下一个
list.remove(list.size()-1);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int[] arr=new int[n];
for (int i = 0;
i < n;
i++) {
arr[i]=sc.nextInt();
}
List sum=new ArrayList<>();
//存储每种组合的和
List list=new ArrayList<>();
//存储组合
list.add(0);
//第一个数为组合的和
rcs(sum,list,k,0,arr);
//回溯
int ans=0;
for (int i = 0;
i < sum.size();
i++) {
if(isPrime(sum.get(i)))
ans++;
}
System.out.println(ans);
} 【算法|回溯算法——洛谷p1036】
推荐阅读
- 2021第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组
- 算法练习|第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组（第一场真题 + 部分题解）
- 蓝桥杯|扩散（十一届蓝桥杯java决赛题目）
- Java|Java 第 24 课 888. 公平的糖果棒交换 720. 词典中最长的单词
- 数据结构设计简单 LeetCode1656. 设计有序流
- #|第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组解析
- 实现一个自己的语法解析器与执行引擎
- 蓝桥杯|2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）（路径）
- 蓝桥杯|2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）（杨辉三角形）