1.面向对象方式
import java.util.Scanner;public class Main {public static class Node{public int value;public int color;public int parent;public Node(int value){this.value = value;this.color = -1;this.parent = -1;}}public static void dfs(Node []node,int cur,int count){count++;if(count==node.length && isPrime(node[cur].value+node[0].value)){node[count-1].parent = node[cur].value;printNode(node);return ;}node[cur].color = 1;for (int i = 0; i < node.length; i++) {if(node[i].color==-1 && isPrime(node[i].value+node[cur].value)){node[count-1].parent = node[cur].value;dfs(node, i, count);node[i].color = -1; }}}private static void printNode(Node[] node) {for (int i = 0; i < node.length-1; i++) {System.out.print(node[i].parent+" ");}System.out.println(node[node.length-1].parent);}public static boolean isPrime(int n){for (int i = 2; i*i <= n; i++) {if(n%i==0){return false;}}return true;}public static Scanner scanner;public static void main(String[] args) {scanner = new Scanner(System.in);int cases = 1;while(scanner.hasNext()){int n = scanner.nextInt();Node node[] = new Node[n];for (int i = 0; i < n; i++) {node[i] = new Node(i+1); }System.out.println("Case "+(cases++ )+":");int count = 0;dfs(node,0,count);//当前位置是0System.out.println();}}}
2.数组方式
import java.util.Scanner;public class Main{private static Scanner scanner;public static void main(String[] args) {scanner = new Scanner(System.in);int cases = 1;while(scanner.hasNext()){int n = scanner.nextInt();int num[] = new int[n];int color[] = new int[n];int parent[] = new int[n];//初始化for (int i = 0; i < n; i++) {num[i] = i+1;parent[i]=-1; }System.out.println("Case "+(cases++ )+":");int count = 0;//搜索的深度dfs(num,color,parent,0,count);//从第0个开始System.out.println();}}//cur当前到了哪一个private static void dfs(int[] num, int[] color, int[] parent,int cur, int count) {count++;//鸿沟if(count==num.length && isPrime(num[0]+num[cur])){parent[count-1] = num[cur]; //设定最后一个的值（不设就是-1了）printNum(parent);return;}color[cur] = 1; //不能直接++for (int i = 0; i < parent.length; i++) {if(color[i]==0 && isPrime(num[i]+num[cur])){parent[count-1] = num[cur];//cur找到了她的下一点count-1dfs(num, color, parent, i, count);color[i] = 0;}}}private static void printNum(int[] parent) {for (int i = 0; i < parent.length-1; i++) {System.out.print(parent[i]+" ");}System.out.println(parent[parent.length-1]);}private static boolean isPrime(int i) {for (int j = 2; j*j <= i; j++) {if(i%j==0){return false;}}return true;}
}