题意

一个由自然数 1…n (n≤18) 素数环就是如下图所示，环上任意两个节点上数值之和为素数。

 　　1

　　/ \

　  4  2

　　\ /

 　   3

Input

输入只有一个数 n，表示你需要建立一个 1…n 的素数环。

Output

按照字典序输出每一种情况。我们约定顺时针为正向，且第一个元素必须是 1。

 

---

 

 

1 #include 
     
       2 #include 
      
        3 int state[19],out[19]={
   0,1}; 4 int primelist[12]={
   2,3,5,7,11,13,17,19,23,29,31,37}; 5 int num; 6 int isprime(int n) 7 { 8     for(int i=0;i<12;i++) 9         if(primelist[i]==n) return 1;10     return 0;11 }12 void bt(int n)13 {14     static int j=1,k;15     int i;16     if(n==1)17         if(isprime(out[1]+out[num]))18         {19             for(k=1;k<=num;k++)20                 printf("%d ",out[k]);21             printf("\n");22         }23 24     for(i=(out[j]+1)%2+2;i<=num;i+=2)25     {26         if(state[i]==1) continue;27         if(isprime(out[j]+i))28         {29             out[++j]=i;30             state[i]=1;31             bt(n-1);32             j--;33             state[i]=0;//back34         }35     }36 37 }38 int main()39 {40     scanf("%d",&num);41     int n=num;42     if(n%2==0)   bt(n);43     return 0;44 }
      
     

 

state数组记录数是否已经被取用，已取过的就不取。

回溯，注意递归的结束条件，以及递归返回的时候能够返回之前的状态