[ACM] TOJ 1054 Jesse's Code （素数判断优化+全排列）

Description

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

Input

 

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

输入0结束。

Output

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

Sample Input

3
1 2 4
0

Sample Output

241
421

 

 

解题思路：

这道题做了近一个上午，总是超时，超时。一开始用的dfs生成全排列，并且用的传统的素数判断，而且果断超时。后来看网上的解题报告，学到了一个函数next_permutation(num,num+n)，库函数自动生成n个数的全排列，很方便，修改后又提交，还是超时。后来又把判断素数进行了优化。先判断是否能被奇数整除，然后在主函数中需要判断是否为素数的时候先需要判断一下是否为偶数。双重判断来确定是否为素数。改了以后，就不超时了。

代码：

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
int jc[10],num[10],n;

void JC()//jc[i]用来保存i个数全排列总个数
{
    jc[1]=1;
    for(int i=2;i<=9;i++)
        jc[i]=i*jc[i-1];
}

bool prime(int n)
{
    if(n==1)return 0;
    int t=(int)sqrt(n);
    for(int i=3;i<=t;i+=2)//素数判断优化，判断是否能被奇数整除。
        if(n%i==0)
        return 0;
    return 1;
}

int main()
{
    JC();
    while(cin>>n&&n)
    {
        int flag=0;
        for(int i=0;i<n;i++)
            cin>>num[i];
        sort(num,num+n);
        if(n==1&&num[0]==2)//2很特殊。需要单独判断一下。
            cout<<2<<endl;
        else if(n==9)//九个数要求不同，则一定为1~9这九个数字组成，数字之和能被3整数，这个数也能被3整除，不是素数
            cout<<"NONE"<<endl;
        else
        {
            for(int i=1;i<=jc[n];i++,next_permutation(num,num+n))//生成jc[n]个全排列
            {
                int k=0;
                for(int j=0;j<n;j++)
                    k=k*10+num[j];
                if(k%2!=0)//判断是否能被偶数整除
                {
                    if(prime(k))//判断是否能被奇数整除
                        {
                            printf("%d\n",k);
                            flag=1;
                        }
                }
            }
            if(!flag)
                cout<<"NONE"<<endl;
        }
        cout<<endl;
    }
    return 0;
}