问题 : Jesse's Code

题目描述

Jesse是个数学迷，他最喜欢研究“哥德巴赫猜想”，因此他的计算机密码也都采用素数。 但一直用同一个密码是不安全的，所以他要经常更换他的密码。但他只允许自己的密码中出现某些数字，且密码的每一位都不相同。比如1 2 4，则有6种情况124 142 214 241 412 421。其中241 和 421为素数。为了获得他的密码（他的机器上存放了第4届舜禹杯大学生程序设计竞赛的题目！），需要生成一个字典来帮助我们破解。 请你来编写一个程序帮助我们（因为众所周知的原因我们迫切需要获得这些题目）。

输入

• Line 1:密码的位数n (1 ≤ n ≤ 9)。
• Line 2:1->n个不重复的整数序列 (1 ≤ x[i] ≤ 9).

输入0结束。

输出

按从小到大顺序输出所有的结果。 如果一个结果也没有，输出“NONE”。 每组数据后面跟随一个空行。

样例输入

3
1 2 4
0

样例输出

241
421

先进行全排列, 然后找素数.

代码：

# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;
int n, c, d;
int a[10], book[10], q[10];

int qwe(int x)  // 判断素数
{
	int b = 0, i;
	for (i = 2; i <= x/2; i ++)
	{
		if (x % i == 0)
		return 0;
	}
	if (x == 1)
	return 0;
	
	return 1;
}

void dfs(int cur)
{
	int k, i;
	if (cur == n+1)
	{
		d = 0;
		for (i = 1; i <= n; i ++)  // 排列后的和
		{
			d = d*10 + q[i];
		}
		if (qwe(d) == 1)  // 如果是素数
		{
			printf("%d\n", d);
			c = 1; // 标记变量 ,  看是否有素数
		}
		return;
	}
	for (k = 1; k <= n; k ++)
	{
		if (book[k] == 0)
		{
			book[k] = 1;
			q[cur] = a[k];
			dfs(cur+1);
			book[k] = 0;
		}
	}
	return;
}
int main(void)
{
	while (~ scanf("%d", &n))
	{
		int i;
		if (n == 0)
			break;
		for (i = 1; i <= n; i ++)
			scanf("%d", &a[i]);
		memset(book, 0, sizeof(book));
		sort(a+1, a+1+n);
		c = 0;
		dfs(1);
		if (c == 0)
		printf("NONE");
	}
	return 0;
}