joj 1195

1195: Prime Ring Problem


Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
10s
8192K
1973
499
Standard
A ring is composed of n circles as shown in diagram. Put natural numbers 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 <iostream>
#include <cmath>


using namespace std;
const int maxn = 33;




int isp[maxn], n, a[10000],vis[10000];
bool judge(int x)
{
	int i;
	for (i=2; i<=sqrt((double)x); i++)
	{
		if (x % i == 0) return false;
	}
	return true;
}


void makeprime()
{
	int i;
	for (i=2; i<=maxn; i++)
		if (judge(i)) isp[i] = 1;
		
}


void dfs(int cur)
{
	if (cur == n && isp[a[0]+a[n-1]]==1)
	{
		int i;
		cout<<a[0];
		for (i=1;i<n; i++)
		{
			cout<<" "<<a[i];
		}
		cout<<endl;
	}
	else
	{
		int i;
		for (i=2; i<=n; i++)
		{
			if (!vis[i] && isp[i+a[cur-1]] == 1)
			{
				a[cur] = i;
				vis[i] = 1;
				dfs(cur+1);
				vis[i] = 0;
			}
		}
	}
	
}


int main()
{
	makeprime();
	int count=0;
	while (cin>>n)
	{
		count++;
		cout<<"Case "<<count<<":"<<endl;
		if(n%2==0)
		{
			memset (a,0,sizeof(a));
			memset (vis,0,sizeof(vis)); 
			vis[1] = 1;
			a[0] = 1;
			dfs(1);
		}
			cout<<endl;
		
	}
	return 0;
}

좋은 웹페이지 즐겨찾기