题目链接：
题解：
直接枚举复杂度是O（n!*n），原地爆炸。我们考虑优化。
直接枚举过程中可以判断前后是不是素数，进行剪枝，复杂度O（7!）（15以内的素数有7个），可过。
或者我们直接枚举素数，复杂度同上。
注意：第一个数要特判，因为不特判的话只能计算第一个数是素数的方案。
1 #include2 #include 3 #include 4 #define LL long long 5 #define RI register int 6 using namespace std; 7 const int INF = 0x7ffffff ; 8 const int N = 15 + 2 ; 9 10 inline int read() {11 int k = 0 , f = 1 ; char c = getchar() ;12 for( ; !isdigit(c) ; c = getchar())13 if(c == '-') f = -1 ;14 for( ; isdigit(c) ; c = getchar())15 k = k*10 + c-'0' ;16 return k*f ;17 }18 int n, cnt = 0, tot = 0 ; int prime[N], ans[N] ; bool p[N*N], vis[N] ;19 20 inline void Prime_() {21 memset(p,0,sizeof(p)) ;22 for(int i=2;i<=(N<<1);i++) { 23 if(!p[i]) prime[++cnt] = i ;24 for(int j=1;j<=cnt&&prime[j]*i<=(N<<1);j++) {25 p[i*prime[j]] = 1 ; 26 if(i%prime[j] == 0) break ;27 }28 }29 // for(int i=1;i<=cnt;i++) printf("%d\n",prime[i]) ;30 }31 32 void dfs(int now,int pre_prime,int pre_num) {33 if(now == n+1) {34 tot ++ ; for(int i=1;i<=n;i++) printf("%d ",ans[i]) ; printf("\n") ;35 }36 if(now == 1) {37 for(int i=1;i<=n;i++) {38 vis[i] = 1 ; ans[now] = i ;39 dfs(now+1,0,i) ; vis[i] = 0 ;40 }41 return ;42 }43 for(int i=1;i<=cnt;i++) {44 if(prime[i] == pre_prime) continue ;45 int t = prime[i]-pre_num ; if(vis[t] || t > n || t <= 0) continue ;46 vis[t] = 1 ; ans[now] = t ;47 dfs(now+1,prime[i],t) ;48 vis[t] = 0 ;49 }50 }51 52 inline void init_() {53 n = read() ; Prime_() ;54 dfs(1,0,0) ;55 printf("%d",tot) ;56 }57 58 int main() {59 // freopen("dfs3.in","r",stdin) ;60 // freopen("dfs3.out","w",stdout) ;61 init_() ;62 return 0 ;63 }