【题目描述】
输入正整数n，把整数1,2,…,n 组成一个环，使得相邻两个整数之和均为素数。
【输入】
输入正整数n。
【输出】
输出任意一个满足条件的环。
【输入样例】
6【输出样例】
4 3 2 5 6 1【提示】
数据满足：
4≤n≤30
#include <bits/stdc++.h>
using namespace std;
int v[31],a[31],n;
bool isPrime(int n)
{
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)
return false;
return true;
}
bool isPrimePair(int pos)
{
if(pos==1)
return isPrime(pos);
else if(pos==n)
return isPrime(a[1]+a[n]);
return isPrime(a[pos-1]+a[pos]);
}
void dfs(int cnt)
{
if(cnt>1&&isPrimePair(cnt)==false ) //新填的数不构成素数环，退出
return;
if(cnt==n&&isPrimePair(n))
{
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
exit(0); //只需要一种，程序强制退出
}
for(int i=1;i<=n;i++)
{
if(v[i]==0 ) //没有被访问且与上一个元素之和相加是素数
{
a[cnt+1]=i;
v[i]=1; //标记已填过数了
dfs(cnt+1);
v[i]=0;// 回溯
}
}
}
int main()
{
cin>>n;
a[1]=1;
v[1]=1;
dfs(1);
return 0;
}
标签：5.1,信奥,int,素数,通题,return,输入 From： https://www.cnblogs.com/nanshaquxinaosai/p/18415938