Jesse's Code （排列素数判断）

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

输入格式

第一行输入密码的位数$n(1\le n\le 9)$。

第二行输入 $1-n$ 个不重复的整数序列 $(1\le x[i]\le 9)$.

输入以 $0$ 结束。

输出格式

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

样例输入

3
1 2 4
0

样例输出

241
421

思路：

生成排列，判断是否为素数(数字比较大的时候，如果是2或3的倍数肯定不是素数直接跳过)

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int check(long long s)
{
	int i,j;
	for (i=3; i*i<=s; i+=2)
	{
		if (s%i==0)
		return 0;
	}
	return 1;
}
int main()
{
    long long i,j,k,n,a[11],s,flag=1;
    while (cin>>n)
    {
    	if (n==0)
    	 break;
	    for (i=0; i<n; i++)
	    cin>>a[i];
	    flag=1;
		sort(a,a+n);
		do
		{
		    s=0;
		    for (i=0; i<n; i++)
		    {
		        s = s*10 + a[i];
		    }
		    if (s%2!=0 && s%3!=0)
		    {
		    	if (check(s))
		    	{
		    		flag=0;
		    		cout<<s<<endl;
				}
			}
		}while (next_permutation(a,a+n));
		if (flag)
		{
		    cout<<"NONE"<<endl;
		}
	}

    return 0;
}