hdu 素数环

全排列dfs的拓展

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n, val[1010], hasht[1010];
bool isprime(int n)
{
	if (n <= 1) return false;
	int sqr = sqrt(n);
	for (int i = 2; i <= sqr; i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}
void dfs(int a)
{
	if (a == n && isprime(val[0] + val[n - 1]))
	{
		for (int i = 0; i < n; i++)
			cout << val[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 2; i <= n; i++)
	{
		if (!hasht[i])
		{
			if (isprime(i + val[a - 1]))
			{
				hasht[i] = true;
				val[a] = i;
				dfs(a + 1);
				hasht[i] = false;
			}
		}
	}
}
int main()
{
	int k = 0;
	while (cin>>n) {
		memset(val, 0, sizeof(val));
		memset(hasht, 0, sizeof(hasht));
		printf("Case %d:
", k++);
		val[0] = 1;
		dfs(1);
	}
	
}