原文地址：

一. 问题描述

把从1到n（n>=2）这n个数摆成一个环，要求相邻的两个数的和是一个素数，找出所有满足条件的环。

二. 问题分析

1> 解向量：<x1, x2, ··· , xn>

2> 解空间树：排列树，(n-1)!个叶子结点

3> 剪枝函数：isPrime( x[t-1]+x[t] )，t=2,3,···,n  约束函数

三. 算法实现

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 int n;//素数环中的数字个数 6 int sum=0;//可行方案数 7 int arr[100];//存放素数环 8  9 bool isPrime(int x)10 {11     int i;12     int k=(int)sqrt(x);13     for(i=2;i<=k;i++)14     {15         if(x%i==0)16         {17             return false;18         }19     }20     return true;21 }22 23 //回溯法24 void backtrack(int t)25 {26     int i;27     if(t>n)//搜索到叶子结点28     {29         if(isPrime(arr[n]+arr[1]))30         {31             sum++;32             for(i=1;i<=n;i++)33             {34                 cout<
       
        <<" ";35             }36             cout<
        
         >n)58     {59         sum=0;60         for(i=1;i<=n;i++)61         {62             arr[i]=i;63         }64         backtrack(1);65         cout<<"可行方案数为:"<
         
          <