Description

从1~n（2<=n<=10）这n个数，摆成一个环，要求相邻的两个数的和是素数，按照由小到大请输出所有可能的摆放形式。 比如：n = 4，输出形式如下

1:1 2 3 4 
2:1 4 3 2 
3:2 1 4 3 
4:2 3 4 1 
5:3 2 1 4 
6:3 4 1 2 
7:4 1 2 3 
8:4 3 2 1 
total:8

比如：n = 6，输出形式如下

1:1 4 3 2 5 6 
2:1 6 5 2 3 4 
3:2 3 4 1 6 5 
4:2 5 6 1 4 3 
5:3 2 5 6 1 4 
6:3 4 1 6 5 2 
7:4 1 6 5 2 3 
8:4 3 2 5 6 1 
9:5 2 3 4 1 6 
10:5 6 1 4 3 2 
11:6 1 4 3 2 5 
12:6 5 2 3 4 1 
total:12

Input Format

一个整数n（2<=n<=10）

Output Format

前若干行，每行输出一个素数环的解，最后一行，输出解的总数

4

1:1 2 3 4
2:1 4 3 2
3:2 1 4 3
4:2 3 4 1
5:3 2 1 4
6:3 4 1 2
7:4 1 2 3
8:4 3 2 1
total:8

Source

回溯