又是同学提问的一题，帮他解决了。
将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，
结果均为素数，那么这个环就成为素数环。
n=20时，下面的序列就是一个素数环：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
任意输入n，求满足n的所有素数环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| public class 素数圈 {
static int[][] data;
static boolean[] vis;
static long t;
public static void main(String[] args) {
int n=18;
data=new int[n+1][n+1];
int[] arr=new int[n];
for (int i = 1; i <= n; i++) {
int t=0;
for (int j = 1; j <= n; j++) {
if(getSuNum(i+j)){
data[i][t]=j;
t++;
}
}
}
vis=new boolean[n+1];
for (int i = 0; i <= n; i++) {
vis[i]=false;
}
arr[0]=1;
dfs(1,data,arr,1);
System.out.println(t);
}
private static void dfs(int i, int[][] data,int[] arr,int k) {
if(k>arr.length-1){
// for (int j = 0; j < arr.length; j++) {
// System.out.print(arr[j]+" ");
// }
// System.out.println();
t++;
return;
}
for (int j = 1; j < data.length && data[i][j]!=0; j++) {
if(vis[data[i][j]]==true) continue;
vis[data[i][j]]=true;
arr[k]=data[i][j];
dfs(data[i][j],data,arr,k+1);
vis[data[i][j]]=false;
}
}
private static boolean getSuNum(int num) {
for (int i = 2; i < num; i++) {
if(num%i==0)
return false;
}
return true;
}
}
|