http://poj.org/problem?id=2034題目大意：
給定0<m<n<=1000,1<d<11,求出m到n內的數的一個排列：
使得連續的大于2小于等于d的長度的數字之和是合數。
#include<stdio.h>
#include<string.h>
#include<math.h>
int p[500005];
int ans,a[1005],b[1005],sum[10005];
int m,n,d;
int GetPri()
{
int i,j;
memset(p,0,sizeof(p));
p[1]=1;
i=2;
while (i<=500000)
{
while (p[i]) i++;
j=i+i;
while (j<=500000)
{
p[j]=1;
j+=i;
}
i++;
}
}
int dfs(int dep)
{
int i,k,flag;
if (ans)
return 0;
if (dep==n-m+2)
{
ans=1;
for (i=1;i<n-m+1 ;i++ )
printf("%d,",a[i]);
printf("%d\n",a[i]);
return 0;
}
for (i=m;i<=n ;i++ )
{
if (!b[i])
{
flag=1;
for (k=2;k<=d ;k++ )
{
if (k<=dep&&!p[sum[dep-1]-sum[dep-k]+i])
flag=0;
if (!flag||k>dep)
break;
}
if (!flag)
continue;
a[dep]=i;
sum[dep]=sum[dep-1]+i;
b[i]=1;
dfs(dep+1);
b[i]=0;
}
}
}
int main()
{
GetPri();
while (scanf("%d%d%d",&m,&n,&d)==3)
{
if (!m&&!n&&!d)
break;
ans=0;
memset(sum,0,sizeof(sum));
memset(b,0,sizeof(b));
dfs(1);
if (!ans)
printf("No anti-prime sequence exists.\n");
}
return 0;
}
水過一題。dfs還是很好寫的哈