# UVA 12218 An Industrial Spy
## 題目連結 [UVA 12218](https://vjudge.net/problem/UVA-12218)
### 題目內容
Industrial spying is very common for modern research labs. I am such an industrial spy - dont tell anybody! My recent job was to steal the latest inventions from a famous math research lab. It was hard to obtain some of their results but I got their waste out of a document shredder.

I have already reconstructed that their research topic is fast factorization. But the remaining paper snippets only have single digits on it and I cannot imagine what they are for. Could it be that those digits form prime numbers? Please help me to find out how many prime numbers can be formed using the given digits.
### 輸入限制
The first line of the input holds the number of test cases c (1 ≤ c ≤ 200). Each test case consists of a single line. This line contains the digits (at least one, at most seven) that are on the paper snippets.
### 輸出限制
For each test case, print one line containing the number of different primes that can be reconstructed by shuffling the digits. You may ignore digits while reconstructing the primes (e.g., if you get the digits 7 and 1, you can reconstruct three primes 7, 17, and 71). Reconstructed numbers that (regarded as strings) differ just by leading zeros, are considered identical (see the fourth case of the sample input).
### 解題思路
1.題目描述為給你一個數字，查看它的所有排列組合看有多少種可能為質數的值
2.題目規定數字大小為最大不能超過7位數
3.先建一個質數表
4.記得在算之前要先sort
5.p陣列用來儲存全部子集
6.利用set來儲存排列中可能為質數的值
7.利用next_permutation算出每個子集的所有排序可能
8.最後set陣列大小即為答案

解法二為利用dfs代替next_permutation
### 程式碼

#include<bits/stdc++.h>
using namespace std;
int prime[10000005];
void Prime(){
    for(int i=0;i<10000005;i++){
        prime[i]=1;
    }
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<=10000005;i++){
        if(prime[i]==1){
            for(int j=i+i;j<=10000005;j+=i){
                prime[j]=0;
            }
        }
    }
}
int main(){
    Prime();
    string s;
    int n;
    cin>>n;
    while(n--){
        cin>>s;
        int len=s.length();
        string p[1000];
        set<int>q;
        memset(p,0,sizeof p);
        sort(s.begin(),s.end());
        for(int i=0;i<pow(2,len);i++){
            for(int j=0;j<len;j++){
                if(i&(1<<j)){
                    p[i]+=s[j];
                }
            }
        }
        for(int i=1;i<pow(2,len);i++){
            do{
                if(prime[stoi(p[i])]==1){
                    q.insert(stoi(p[i]));
                }
        }while(next_permutation(p[i].begin(),p[i].end()));
        }
        cout<<q.size()<<endl;
    }
}

### 解法二

#include<bits/stdc++.h>
using namespace std;
int prime[10000005];
void Prime(){
    for(int i=0;i<10000005;i++){
        prime[i]=1;
    }
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<=10000005;i++){
        if(prime[i]==1){
            for(int j=i+i;j<=10000005;j+=i){
                prime[j]=0;
            }
        }
    }
}
string q;
set<int>z;
bool vis[10000005];
void dfs(int step,int len,string s){
    if(step==len+1){
        if(prime[stoi(q)]==1){
            z.insert(stoi(q));
        }
    }
    for(int i=0;i<len;i++){
        if(vis[i]!=true){
            q.push_back(s[i]);
            vis[i]=true;
            dfs(step+1,len,s);
            vis[i]=false;
            q.pop_back();
        }
    }
}
int main(){
    Prime();
    string s;
    int n;
    cin>>n;
    while(n--){
        z.clear();
        cin>>s;
        int len=s.length();
        sort(s.begin(),s.end());
        for(int i=1;i<pow(2,len);i++){
            string p="";
            for(int j=0;j<len;j++){
                if(i&(1<<j)){
                    p.push_back(s[j]);
                }
            }
            dfs(1,p.length(),p);
        }
        cout<<z.size()<<endl;
    }
}

## 測資
### Sample input
4
17
1276543
9999999
011
### Sample output
3
1336
0
2