预处理出前4位的超级素数，再枚举后四位
View Code
1 /* 2 ID: your_id_here 3 PROG: sprime 4 LANG: C++ 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<cmath> 10 #include<algorithm> 11 using namespace std; 12 int num[10][1000],f[20],g,n,k[10],nn[10000],kk; 13 int prime(int x) 14 { 15 if(x==1) 16 return 0; 17 int k = sqrt(x),i,flag = 1; 18 for(i = 2 ;i <= k ;i++) 19 if(x%i==0) 20 { 21 flag =0; 22 break; 23 } 24 return flag; 25 } 26 void dfs(int x , int v) 27 { 28 int y = x,i; 29 if(!prime(x)) 30 return ; 31 if(v==n) 32 { 33 if(prime(x)) 34 { 35 kk++; 36 nn[kk] = x; 37 } 38 return ; 39 } 40 for(i = 0 ; i <= 9 ; i++) 41 { 42 x = x*10+i; 43 dfs(x,v+1); 44 x = y; 45 } 46 } 47 int main() 48 { 49 freopen("sprime.in","r",stdin); 50 freopen("sprime.out","w",stdout); 51 int i,j; 52 cin>>n; 53 num[1][0] = 2; 54 g = 0; 55 for(i = 3; i <= 9 ; i++) 56 if(prime(i)) 57 num[1][++g] = i; 58 k[1] = g; 59 g = -1; 60 for(i = 11 ; i <= 99 ; i++) 61 { 62 if(prime(i/10)&&prime(i)) 63 num[2][++g] = i; 64 } 65 k[2] = g; 66 g = -1; 67 for(i = 101 ; i <= 999 ; i++) 68 { 69 if(prime(i/10)&&prime(i)&&prime(i/100)) 70 num[3][++g] = i; 71 } 72 k[3] = g; 73 g = -1; 74 for(i = 1001 ; i <= 9999 ; i++) 75 { 76 if(prime(i/10)&&prime(i)&&prime(i/100)&&prime(i/1000)) 77 num[4][++g] = i; 78 } 79 k[4] = g; 80 if(n<=4) 81 { 82 for(i = 0 ; i <= k[n] ; i++) 83 cout<<num[n][i]<<endl; 84 } 85 else 86 { 87 for(i = 0 ; i <= k[4] ; i++) 88 { 89 dfs(num[4][i],4); 90 } 91 sort(nn+1,nn+kk+1); 92 for(i = 1; i <= kk ; i++) 93 cout<<nn[i]<<endl; 94 } 95 fclose(stdin); 96 fclose(stdout); 97 return 0; 98 }