本学期的计算机系统实验课程中遇到质数环问题，需要编写程序求解并在ARM多核开发系统上开展实验。以下是我通过搜索得到的两种解法，第一种利用C语言编写，只能输出20个数字的质数环；第二种解法利用C++编写，可以输出小于等于20个数字的质数环。

解法一：

//我们可以通过改变n的值来求不同数字范围的质数环，如果超出整型的范围，还需要改变数据类型。//p[i][j]用来记录数字i和数字j的和是否为质数，f[i]来记录数字i是否使用过，//T[i]用来记录下一个可以插在数字i后面的与其和为质数的数字在P[i][]中的位置。//用F[i][j]来存储按数字从小到大的顺序得出的与数字i和为质数的第j个数字，//例如：F[1][2]存储的是与数字1的和为质数的第二个数字，我们可以通过查询数组P[][]的第一行找出第二个不为0//值，然后将当前数组单元的列号存储到F[1][2]中，即F[1][2] = 4。//算法思想是通过查询二维数组F[][]，来确定下一个可以插入数组C[]的未使用过的数字，并记录该数字位于数组F[][]的位置，//以便回溯时寻找下一个符合要求的数字。如果不存在这样的未使用的数字，则需要回溯到上一个已插入C[]的数字，//寻找下一个可以插在该数字后面的未使用过的数字进行插入，如果所有的数字都已经插入到C[]中，//那么还要判断首尾数字相加之和是否为质数，如是则打印结果。当所有数字都已插入C[]中，开始//进行回溯，重复上述操作，寻找其他符合要求的序列。#include"stdafx.h"#include
    
     #include
     
      #include
      
       #include
       
        void main(){   int  P[21][21], F[21][21], f[21], T[21], C[20];   //20个数   int i, j, k, t, temp, p, flag, n, c;   double duration;   clock_t start, finish;   start = clock();   n = 20;   c = 20000;   for(i = 1; i <= n; i++)   {	   k=1;	   for(j = 1; j <= n; j++)	   {		   P[i][j] = 0;                              //数组初始化		   F[i][j] = 0;		   if(j != i && ((int)abs((i-j) % 2)) != 0)  //i和j一奇一偶		   {			   temp = i + j;			   t = (int) sqrt((double)(temp) + 1);//求i和j和的平方根			   for(p = 2; p <= t; p++)			   {				   P[i][j] = 0;				   if(! (temp % p)) break;     //判断temp是否是质数，如果temp是质数，则P[i][j]为1				   P[i][j] = 1;                      			   }		   }		   if(P[i][j])                               //如果i和j的和为质数则		   {                                         //记录与数字i和为质数的第k个数字j			   F[i][k] = j;                          			   k++;		   }	   }   }      //for(i = 1; i <= n && c; i++)   for(i=1; i<=n; i++)   {	   C[0] = i;	   for(p = 1; p <= n; p++)	   {		   T[p] = 1;                                 //T[i]用来记录下一个可以插在数字i后面的与其和为质数的数字在F[i][]中的位置。		   f[p] = 0;                                 //f[i]记录数字i是否使用过，0表示未使用过，1表示使用过	   }	   f[i] = 1;	   k = 1;	   while(k)	   {		   while(F[i][T[i]] && k < n)               //F[i][T[i]]表示存在与i和为质数的数字并且可以插在数字i后面		   {			   if(! f[F[i][T[i]]])              //f[F[i][T[i]]]判断如果数字F[i][T[i]]没有使用过			   {				   C[k] = F[i][T[i]];        //记录质数环的数字				   f[C[k]] = 1;				   T[i]++;				   i = C[k];				   k++;			   }			   else;			   T[i]++;		   }		   if(k == n)                               //判断C[0]和C[n-1]的和是否为质数		   {			   temp = C[0] + C[n-1]; 			   t = (int) sqrt((double)(temp) + 1);			   for(p = 2; p <= t; p++)			   {				   flag = 0;				   if(! (temp % p)) break;				   flag = 1;                 //如果C[0]和C[n-1]的和为质数，则flag为1			   }			   if(flag)			   {				   c--;				   for(p = 0; p < n; p++)				   {					   printf("%d- ",C[p]);				   }				   printf("\n");			   }		   }		   		   f[C[--k]] = 0;                       //回溯		   T[C[k]] = 1;           i = C[k-1];	       if(!c)                                  //如果c为0，则k为0，此时结束while循环，即至多寻找20000个质数环			   k=0;	   }//end while   }//end for   finish=clock();   duration = (double)(finish - start) / CLOCKS_PER_SEC;    printf( "%f seconds\n", duration ); }//end main
       
      
     
    

解法二：

/*********************************************************************** 分析: 1、每个环都从1开始，先将数组a[0]赋值1. 2、每选定前一个素数，后一个位置就少一个可选择项，由此可用一个数组bUsed[]来标记状态. 3、前一个后一个选定值总和前一个选定值关联，由此可用回溯法(深度优先遍历的方式遍历解答树)。 ************************************************************************/  #include "stdafx.h"#include 
    
       #include 
     
        using namespace std;  int n=0;int a[20];  bool bUsed[20];//对应数组a[20],判断对应节点在当前求得素数环中(解答树)是否有它    /*判断是素数*/  bool isp(int n){      if(n<3)          return false ;      int len=(int)sqrt(n+0.0);      for (int i=2;i<=len;i++){          if(n%i==0)              return false ;      }      return true;  }    /*递归输出所有素数环*/  void AA(int cur){      //在最后一层执行,输出当前求得解答串      if(cur==n&&isp(a[0]+a[n-1])){          for (int i=0;i
      
       >n,n){          AA(1);              //回溯法遍历解答树,输出所有素数环      }  }
      
     
    

优化思路：可以通过一些规则进行剪枝，能够提高搜索效率。

1、对于输入的n，如果输入n是奇数的话，则没有满足条件的质数环。

if(n & 1) // 奇数无解，直接返回    return ;

2、相邻的两个数奇偶性必然不同。

if(!((a[0] + a[n-1]) & 1)) // 相邻的数奇偶性必然不同     return false ;