USACO Section 1.5 Superprime Rib

枚舉不可以，逾時，加了剪枝，還是沒有什麼效果。

不如生成，每次在數的末尾加上1,3,7,9，如果是素數，再繼續加，直到加到長度滿足為止，效率大大提高

1 /* ID:linyvxi1
 2    PROB:sprime
 3    LANG:C++
 4 */
 5 #include <stdio.h>
 6 int n;
 7 bool prime(int num)
 8 {
 9     if(num==1)
10         return false;
11     if(num==2)
12         return true;
13     int i;
14     for(i=2;i*i<=num;i++){
15         if(num%i==0){
16             return false;
17         }
18     }
19     return true;
20 }
21 void dfs(int num,int len)
22 {
23     if(len==n){
24         if(prime(num)){
25             printf("%d\n",num);
26         }
27         return;
28     }
29     if(!prime(num)){
30         return;
31     }
32     dfs(num*10+1,len+1);
33     dfs(num*10+3,len+1);
34     dfs(num*10+7,len+1);
35     dfs(num*10+9,len+1);
36 }
37 int main()
38 {
39     freopen("sprime.in","r",stdin);
40     freopen("sprime.out","w",stdout);
41     scanf("%d",&n);
42     if(n==1){
43         printf("2\n3\n5\n7\n");
44         return 0;
45     }
46     dfs(2,1);
47     dfs(3,1);
48     dfs(5,1);
49     dfs(7,1);
50 }