回溯法求解素数环问题的时间复杂度分析

其时间复杂度应该是O(!n)因为需要找到满足素数环的所有条件的取值，等价于找到2～n的其中一个排列。

C++的回溯素数环：

#include
using namespace std;
int n;
int a[20];
bool vist[20];
bool isPrime(int x){
	if(x < 2) return false;
	for(int i = 2; i*i <= x; i++){
		if(x%i == 0) return false;
	}
	return true;
}
void print(){
	for(int i = 0; i <= n-1; i++){
		cout << a[i] << " ";
	}
	cout << endl;
}
void dfs(int cur){
	int i;
	if(cur == n && isPrime(a[n-1]+a[0])){
		print();
		return;
	}
	for(i = 2; i <= n; i++){
		if(!vist[i]&&isPrime(i+a[cur-1])){
			a[cur] = i;
			vist[i] = 1;
			dfs(cur+1);
			vist[i] = 0;
		}
	}
}
int main(){
	cin >> n;
	if(n%2 == 0){
		a[0] = 1;
		vist[1] = 1;
		dfs(1);
	} 
	return 0;
}