素数环

昨天晚上，突然想读刘汝佳老师书中的例题，素数环，但是突然自己就有了思路，于是便自己实现了一下。但是，由于昨晚时间比较晚，程序是写完了，但是没调试出来，今天一大早就开始调试，花了半小时终于调试出来了，好开心！

中心思想是：回溯

上代码：

#include<iostream>
#include<math.h>
using namespace std;
int visit[17]; //注意0号位置的存储位置不使用 
int m;  //存储的是输入的参变量 
int frq[17];
bool judePrime(int n); //判断是否是素数
bool dfs(int n);//使用深度优先遍历的方法进行查看 
int main(){
	int n=1;  //标志着填写到frq的哪一位 
	cout << "请输入m的值";
	cin >> m; 
	frq[n] = 1; 
	visit[n] = 1; //标志着1号位置已经被访问 
	dfs(2);
	
}

bool dfs(int n){ //注意n第一次进来的时候必须是2 
	if (n > m){
		for (int i=1; i<=m; i++){
			cout<<frq[i]; 
		}
		cout << endl;
		return true;
	}
	
	for (int i=2; i<=m; i++){ //每个位置都有可能是2-m上的数字 
		int temp = i + frq[n-1];
		if (i!=m && visit[i]==0){ //当 i不是最后一个元素，并且i没有被访问过 
 			if (judePrime(temp)){ //如果是素数 
				frq[n] = i;
				visit[i] = 1; //标志其已经被访问过
				n++;
				dfs(n);
				--n;
				frq[n] = 0;
				visit[i] = 0;
			}
		}else if(i==m && visit[i]==0){
				int temp2 =  i + frq[1];
				if (judePrime(temp) && judePrime(temp2)){ //因为所有的数围成的是一个环，所以
				//当填写到最后一个数的时候，要判断和第一个数相加是否满足和为素数 
					frq[n] = i;
					visit[i] = 1;
					n++;
					dfs(n);
					--n;
					frq[n] = 0;
					visit[i] = 0;
				}
			}
		
	}
} 
bool judePrime(int n){ //判断一个数是否是素数 
	int temp =sqrt(n);  
	for (int i=2;  i<=temp; i++){
		if (n%i ==0){
			return false;
		}
	}
	return true;
}