HDU1016 Prime Ring Problem DFS

　　简单DFS，需要注意的是最后的那个数加上一要是个素数。

　　代码如下：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

int hash[25], rec[25], cnt;

bool isprime( int x )
{
	if( x<= 1 ) return false;
	if( x== 2 ) return true;
	int lim= sqrt( x );
	for( int i= 2; i<= lim; ++i )
	{
		if( x% i== 0 ) return false;
	}
	return true;
}

void DFS( int last, int cnt, int N )
{
	if( cnt== N )
	{
		if( isprime( rec[N- 1]+ 1 ) )
		{
			for( int i= 0; i< cnt; ++i )
			{
				printf( i== 0? "%d": " %d", rec[i] );
			}
			puts( "" );
		}
		return;
	}
	for( int i= 1; i<= N; ++i )
	{
		if( !hash[i]&& isprime( last+ i ) )
		{
			rec[cnt]= i;
			hash[i]= 1;
			DFS( i, cnt+ 1, N );
			hash[i]= 0;
		}
	}
}

int main()
{
	int N, ca= 0;
	while( scanf( "%d", &N )!= EOF )
	{
		rec[0]= 1;
		hash[1]= 1;
		printf( "Case %d:\n", ++ca );
		DFS( 1, 1, N );
		puts( "" );
	}
	return 0;
}