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 8Sample 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 题意： 给出一个数n，求1到n的数形成一个环，这个环相邻两数和是素数，按字典顺序输出 细节看代码 #include<iostream> #include<vector> #include<algorithm> #include<math.h> #include<string> using namespace std; int n,b[21]={1,1},a[21]={0,1},cnt=1,c[41]={0,0,1,1};//c[]标记素数，b[]标记数是否用过，a[]用于存储输出 int sushu(int x)//判断素数 { for(int i=2;i<=sqrt(x);i++) { if(x%i==0) return 0; } return 1; } void print()//输出 { cout<<a[1]; for(int j=2;j<=n;j++) { cout<<" "<<a[j]; } cout<<endl; } void solve(int x)//深搜 { for(int i=2;i<=n;i++) { if((c[a[x-1]+i])&&(!b[i]))//判断放下数后与前数和还是素，没用过此数 { b[i]=1; a[x]=i; if(x==n) { if(c[a[1]+a[x]]) {print();} } else {solve(x+1);} b[i]=0; } } } int main() { for(int i=4;i<=40;i++)//因n最大20，故预处理出40内的素数 { if(sushu(i)) c[i]=1; } while(cin>>n) { cout<<"Case "<<cnt<<":"<<endl; cnt++; solve(2); cout<<endl; } return 0; }