巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。

排序方法：以贪心算法进行搜索，由于两个数字之和是一个素数，且首尾两数字之和也为一个素数，因此只需要找出以1开头的排列就可以了。使用贪心算法的同时使用回溯法，当遇到相邻两个数的时候就回溯到上一步从新搜索。

ofstream fout("D://Prime.txt",ios::app);
bool ISPrime(int n)
{
	for(int i=2;i<=sqrt((double)n);i++)
		if(n%i==0)
			return false;
	return true;
}
void PrimeArrange(int *arr,int begin,int length)
{
	
	if(begin==length)
	{
		if(ISPrime(arr[begin-1]+arr[0]))
		{
			copy(arr,arr+length,ostream_iterator<int,char>(fout,"  "));
			fout<<"
";
			cout<<endl;
		}
		return;
	}
	else if(begin>1&&!ISPrime(arr[begin-1]+arr[begin-2]))//截枝和回溯
	{
		return;
	}
	else
	{
		for(int i=begin;i<length;i++)
		{
			swap(arr[begin],arr[i]);
			PrimeArrange(arr,begin+1,length);//搜索
			swap(arr[begin],arr[i]);
		}
	}
}
void PrimeArrange(int *arr,int length)
{
	if(arr==NULL||length<=0)
	{
		return;
	}
	PrimeArrange(arr,1,length);
}



int main()
{
	int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	
	PrimeArrange(a,20);
	fout.close();
        cout<<"结束"<<endl;
       return 0;
}

部分结果如下（结果集太大）