import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.StringTokenizer; /** * Created by dhruv.pancholi on 20/11/16. */ public class Main { private static boolean[] onStack = new boolean[16]; private static void dfs(List<Integer>[] adjacency, String out, int node, int n, int N) { if (n == 1) { if (adjacency[node - 1].get(0) == 1) System.out.println(out); return; } for (Integer i : adjacency[node - 1]) { if (onStack[i - 1] || i > N) { continue; } else { out += " " + i; onStack[i - 1] = true; dfs(adjacency, out, i, n - 1, N); out = out.substring(0, out.lastIndexOf(" ")); onStack[i - 1] = false; } } } public static void main(String[] args) throws FileNotFoundException { InputReader in = new InputReader(System.in); SieveOfEratosthenes soe = new SieveOfEratosthenes(50); List<Integer>[] adjacency; adjacency = new List[16]; for (int i = 0; i < 16; i++) { adjacency[i] = new ArrayList<Integer>(); } for (int i = 0; i < 16; i++) { for (int j = i + 1; j < 16; j++) { if (soe.isPrime(i + j + 2)) { adjacency[i].add(j + 1); adjacency[j].add(i + 1); } } } int c = 0; while (true) { LinkedList<Integer> stack = new LinkedList<Integer>(); stack.add(1); onStack[0] = true; int n = in.nextInt(); if (c != 0) System.out.println(); System.out.println("Case " + (++c) + ":"); if (n == 1) { System.out.println(1); } else { dfs(adjacency, "1", 1, n, n); } } } private static class SieveOfEratosthenes { private boolean[] a; public SieveOfEratosthenes(int N) { a = new boolean[N + 1]; for (int i = 0; i <= N; i++) { a[i] = true; } a[0] = false; a[1] = false; int root = (int) Math.sqrt(N); for (int i = 2; i <= root; i++) { for (int j = 2 * i; j <= N; j += i) { a[j] = false; } } } public boolean[] getArray() { return a; } public boolean isPrime(int n) { return a[n]; } public List<Integer> getPrimes() { List<Integer> list = new ArrayList<Integer>(); for (int i = 1; i < a.length; i++) { if (a[i]) { list.add(i); } } return list; } } private static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (Exception e) { System.exit(0); } } return tokenizer.nextToken(); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } } }
Sample Input:
6 8
Sample Output:
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2