首页 > 代码库 > poj 2034 Anti-prime Sequences(dfs)
poj 2034 Anti-prime Sequences(dfs)
//相邻的 2.3......d 之和都要不为素数 # include <algorithm> # include <stdio.h> using namespace std; int num[1010],vis[1010]; int n,m,d,cot; int flag[10010]; void init()//素数打表 { int i,j; for(i=2;i<10010;i++) { if(!flag[i]) for(j=i*i;j<10010;j=j+i) flag[j]=true; } flag[1]=true; flag[0]=true; } bool judge() { int sum,i,k; sum=num[cot-1]; if(cot-d>=0) k=cot-d; else k=0; for(i=cot-2;i>=k;i--) { sum=sum+num[i]; if(!flag[sum])//为素数 return true; } return false; } bool dfs() { int i; if(cot>=2) { if(judge()) return false; } if(cot==m-n+1) return true; for(i=n;i<=m;i++) { if(!vis[i]) { num[cot++]=i; vis[i]=true; if(dfs()) return true; vis[i]=false; cot--; } } return false; } int main() { int i; init();//初判断是否为素数 while(~scanf("%d%d%d",&n,&m,&d),n+m+d) { memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); cot=0; if(dfs()) { for(i=0;i<cot;i++) { if(i==cot-1) printf("%d\n",num[i]); else printf("%d,",num[i]); } } else printf("No anti-prime sequence exists.\n"); } return 0; }
poj 2034 Anti-prime Sequences(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。