【JAVA】第3关：素数链

任务描述
编程要求
测试说明
任务描述
本关任务：把从 1 到 n 这 n 个数摆成一个链，要求相邻的两个数的和是一个素数。

编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务，输出格式请参考测试集。

测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：15
预期输出：摆成的链是: 15 14 9 10 13 6 11 12 7 4 3 8 5 2 1

开始你的任务吧，祝你成功！

package step3;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Prime {// 判断一个数是否为素数private static boolean isPrime(int num) {if (num < 2) {return false; // 小于2的数不是素数}for (int i = 2; i * i <= num; i++) {if (num % i == 0) {return false; // 如果能被整除，则不是素数}}return true; // 否则是素数}// 判断两个数是否可以相连（即它们的和是否为素数）private static boolean canLink(int a, int b) {return isPrime(a + b); // 返回两个数之和是否为素数}// 寻找一个长度为n的链，链中的每两个相邻元素的和都是素数private static List<Integer> findChain(int n) {List<Integer> result = new ArrayList<>(); // 存储结果链boolean[] used = new boolean[n + 1]; // 标记数组，记录哪些数已经被使用// 从n开始向下寻找第一个未使用的数，并将其加入链中for (int i = n; i >= 1; i--) {if (!used[i]) {result.add(i); // 将未使用的数加入链中used[i] = true; // 标记该数为已使用break; // 跳出循环}}// 继续寻找链中的下一个数，直到链的长度达到nwhile (result.size() < n) {int last = result.get(result.size() - 1); // 获取链中的最后一个数boolean found = false; // 标记是否找到下一个数for (int next = n; next >= 1; next--) {if (!used[next] && canLink(last, next)) {// 如果找到一个未使用且可以与最后一个数相连的数，将其加入链中result.add(next);used[next] = true; // 标记该数为已使用found = true; // 标记找到下一个数break; // 跳出循环}}if (!found) {// 如果没有找到下一个数，返回空链return new ArrayList<>();}}return result; // 返回找到的链}public static void main(String[] args) {Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于读取用户输入int n = scanner.nextInt(); // 从用户输入中获取n的值List<Integer> chain = findChain(n); // 寻找长度为n的链System.out.print("摆成的链是: "); // 打印提示信息for (int num : chain) {System.out.print(num + " "); // 打印链中的每个数}System.out.println(); // 换行scanner.close(); // 关闭Scanner}
}