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

╰+哭是因爲堅強的太久メ 2022-06-18 02:42 61阅读 0赞

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

### 输入格式 ###

第一行输入密码的位数n (1 \\leq n \\leq 9)*n*(1≤*n*≤9)。

第二行输入 1-n1−*n* 个不重复的整数序列 (1 \\leq x\[i\] \\leq 9)(1≤*x*\[*i*\]≤9).

输入以 00 结束。

### 输出格式 ###

按从小到大顺序输出所有的结果。如果一个结果也没有，输出`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;
    }