PKU 3842 An Industrial Spy
http://poj.org/problem?id=3842
最大で7つの1桁の数字が与えられる。
この数字のいくつかを並び替えて出来る数字のなかに、素数がいくつあるかを求めるというような問題。
素数を生成して全探索。
bool pr[10000000]; main(){ pr[0]=pr[1]=true; for(int i=2;i<10000000;i++){ if(pr[i])continue; for(int j=2*i;j<10000000;j+=i)pr[j]=true; } int test; cin>>test; while(test--){ string in; cin>>in; sort(ALL(in)); int ans=0; set<int> app; do{ int t=0; rep(i,SZ(in)){ t=t*10+in[i]-'0'; if(!pr[t])app.insert(t); } }while(next_permutation(ALL(in))); cout<<SZ(app)<<endl; } }