Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 31031 Accepted Submission(s): 13755
Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1. 
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order. You are to write a program that completes above process. Print a blank line after each case.
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
简单DFS，给新生讲课用，题目要求顺时针和逆时针输出，实际好像不需要考虑这一点，最后的情况刚好是这样，素数判断用平方根内有无能整除此数的数字来判断。
1 #include2 #include 3 using namespace std; 4 5 int N; 6 int ANS[25]; 7 bool VIS[25]; 8 9 bool isprimer(int n);10 void dfs(int len);11 int main(void)12 {13 int count = 0;14 15 while(cin >> N)16 {17 count ++;18 fill(VIS,VIS + 22,false);19 cout << "Case " << count << ":" << endl;20 dfs(0);21 cout << endl;22 }23 24 return 0;25 }26 27 void dfs(int len)28 {29 if(len == N && isprimer(ANS[len - 1] + ANS[0]))30 {31 for(int i = 0;i < N - 1;i ++)32 cout << ANS[i] << ' ';33 cout << ANS[N - 1];34 cout << endl;35 return ;36 }37 38 for(int i = 1;i <= N;i ++)39 {40 if(!len && i > 1)41 return;42 if(len && !VIS[i])43 {44 if(isprimer(i + ANS[len - 1]))45 {46 ANS[len] = i;47 VIS[i] = true;48 dfs(len + 1);49 VIS[i] = false;50 }51 }52 else if(!len)53 {54 ANS[len] = i;55 VIS[i] = true;56 dfs(len + 1);57 VIS[i] = false;58 }59 }60 61 }62 63 bool isprimer(int n)64 {65 for(int i = 2;i <= sqrt(n);i ++)66 if(n % i == 0)67 return false;68 return true;69 }