题目描述

有一个整数 n，把从 1 到 n 的数字无重复的排列成环，且使每相邻的两个数（包括首和尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从 1 开始。例如，6 的一个素数环：1 4 3 2 5 6。

请编写一个程序，给定一个输入 nn ，如果存在满足要求的素数环，从小到大输出。否则，输出 No Answer。

输入描述

输入整数 n，0<n<20

输出描述

如果存在满足要求的素数环，从小到大输出。否则，输出 No Answer。

样例">样例">样例">样例">样例">样例">输入输出样例

示例

输入

8

输出

1. 1 2 3 8 5 6 7 4 2. 1 2 5 8 3 4 7 6 3. 1 4 7 6 5 8 3 2 4. 1 6 7 4 3 8 5 2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路：

如果n为奇数时，任何一种全排列中必有两个奇数相邻，两个数的和为偶数，不是素数，直接返回“no answer”

采用深度优先搜索的方法得到全排列，设计判别是否为素数的函数判断当前的数和前一轮的数之和是否为素数，用这样的方法进行剪枝。

代码：

1. using namespace std; 2. #include3. #include4. const int N=22; 5. int vis[N]; 6. int c[N]; 7. int n; 8. int ans=0; 9. 10. int is_prime(int x){ 11. if(x<=1) return 0; 12. for(int i=2;i*i<=x;i++){ 13. if(x%i==0){ 14. return 0; 15. } 16. } 17. return 1; 18. } 19. 20. void dfs(int cur){ 21. if(cur==n && is_prime(c[0]+c[n-1])){ 22. ans++; 23. for(int i=0;i<n;i++) cout<<c[i]<<" "; 24. cout<<endl; 25. return; 26. } 27. for(int i=2;i<=n;i++){ 28. if(!vis[i] && is_prime(i+c[cur-1])){ 29. vis[i]=1; 30. c[cur]=i; 31. dfs(cur+1); 32. vis[i]=0; 33. } 34. } 35. } 36. 37. 38. int main(){ 39. cin>>n; 40. c[0]=1; 41. if(n&1){ 42. cout<<"No Answer"<<endl; 43. } 44. else{ 45. dfs(1); 46. if(ans=0) 47. cout<<"No Answer"<<endl; 48. } 49. return 0; 50. }