hdu 1016 Prime Ring Problem
程序员文章站
2022-05-21 08:44:12
...
hdu 1016 Prime Ring Problem
题目传送门
简单搜索问题,这题只要每次判断填的数与前一次填的数相加不为素数,最后一个数则还要考虑与第一个数的和不为素数,这题我打表做的。比较简单
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int a[22];
bool isprime[40];
bool used[21];
void init()
{
memset(isprime, true, sizeof(isprime));
for(int i = 2; i <= 40; ++i)
{
if(isprime[i])
{
for(int j = 2 * i; j <= 40; j += i)
isprime[j] = false;
}
}
}
//当前要填的位置为pos,总共长度为n
void dfs(int pos, int n)
{
//当已经填完n个数后
if(n&1) return;
if(pos == n + 1)
{
if(isprime[a[n]+1])
{
for(int i = 1; i <= n; ++i)
{
printf("%d%c", a[i], i==n ? '\n' :' ');
}
}
return;
}
for(int i = 2; i <= n; ++i)
{
if(!used[i] && isprime[i+a[pos-1]])
{
used[i] = 1;
a[pos] = i;
dfs(pos+1,n);
used[i] = 0;
}
}
}
int main()
{
init();
int n;
a[1] = 1;
int cas = 1;
while(cin >> n)
{
memset(used,false,sizeof(used));
printf("Case %d:\n", cas++);
dfs(2,n);
printf("\n");
}
return 0;
}