hut 1054 Jesse's Code 解题报告

链接：http://oj.innlab.net/JudgeOnline/problem.php?id=1504

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

好久没来了啊。

这道题本质上市一道水题，但我还是纠结了一个晚上，主要是不知道用 next_permutation（）这个强大的函数，纪念一下。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[10];
 7 int fun( int x )
 8 {
 9     for( int i=2; i<=(int)sqrt( x ); ++i )
10     {
11         if( x%i==0 )
12             return 0;    
13     }
14     return 1;    
15 } 
16 
17 int cmp( const void *a , const void *b )
18 {
19     return *( int * )a - *( int * )b;    
20 }
21 
22 int main( )
23 {
24     int n; 
25     int jc[10]={1};
26     for( int i=1; i<=10; ++i )
27     {
28         jc[i]=i*jc[i-1];    
29     }      
30     while( scanf( "%d", &n ) !=EOF, n )
31     {
32         int i, j;
33         if( n == 9 )
34         {
35             puts( "NONE" );//经检验没有素数
36             continue;    
37         }
38         for( i=0; i<n; ++i )
39         {
40             scanf( "%d", &a[i] );    
41         }
42         qsort( a, n, sizeof( a[0] ), cmp );
43         int s, f=1;
44         for(j=0; j<jc[n] ;j++,next_permutation( a,a+n))
45         {
46             
47             s=0;
48             for(i=0;i<n;i++)
49             {
50                  s=s*10+a[i];
51             }
52             if (fun(s))
53             {
54                  printf( "%d\n", s );
55                 f=0;
56             }
57         }
58         if( f )
59             puts( "NONE" );          
60     }    
61     return 0;
62 }