Description
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1,2,3，...，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 <= 16)
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.
You are to write a program that completes above process.
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 【代码】：
/*素数环*/
#include <bits/stdc++.h>
using namespace std;
int n,prime[]={},v[],a[]; void get_prime()
{
int m=sqrt(*n+0.5);//环-倍增
memset(prime,,sizeof(prime));//0为素数
prime[]=prime[]=;//非素数
for(int i=;i<=m;i++)
{
if(prime[i])//素数
{
for(int j=i+i;j<=*n;j+=i)
{
prime[j]=;//非素数
}
}
}
} void dfs(int cur)
{
if(cur == n && prime[ a[]+a[n-] ])
{
for(int i=; i<n; i++)
{
printf("%d%c", a[i], i == n - ? '\n' : ' ');
}
// printf("\n");
}
else
{
for(int i=; i<=n; i++)
{
if( !v[i] && prime[ i + a[cur-] ] )
{
a[cur] = i;
v[i]=;
dfs(cur+);
v[i]=;
}
}
}
}
int main()
{
scanf("%d",&n);
//初始化
memset(v,,sizeof(v));
a[]=; get_prime();
dfs();
}