首页 > 代码库 > Superprime Rib
Superprime Rib
链接
分析:满足题目条件的必然是1,2,3,5,7,9这几个数字的组合,DFS按位进行即可,边组合边判断是否合法。
1 /* 2 PROB:sprime 3 ID:wanghan 4 LANG:C++ 5 */ 6 #include "iostream" 7 #include "cstdio" 8 #include "cstring" 9 #include "string" 10 #include "vector" 11 using namespace std; 12 int n; 13 int a[]={1,2,3,5,7,9}; 14 vector<int> h; 15 bool judge(int x){ 16 if(x<2) return false; 17 if(x==2) return true; 18 for(int i=2;i*i<=x;i++) 19 if(x%i==0) return false; 20 return true; 21 } 22 void dfs(int cur,int num){ 23 if(cur==n){ 24 if(judge(num)) h.push_back(num); 25 return; 26 } 27 if(!judge(num)) return ; 28 else{ 29 //num*=10; 30 for(int i=0;i<6;i++) 31 dfs(cur+1,num*10+a[i]); 32 } 33 } 34 int main() 35 { 36 freopen("sprime.in","r",stdin); 37 freopen("sprime.out","w",stdout); 38 cin>>n; 39 for(int i=0;i<6;i++) 40 dfs(1,a[i]); 41 int len=h.size(); 42 for(int i=0;i<len;i++) 43 cout<<h[i]<<endl; 44 }
Superprime Rib
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。