# 題目: UVa 12218 - An Industrial Spy

# 題目說明

給一個至多 7 位的數，求每個數字排列後，為質數的數量

例如: 17
可以排成: 1、7、17、71
共有 7、17、71 3 個質數

INPUT:
第一行輸入一個整數 N ，代表測資數
每筆測資輸入一個至多 7 位的數 str

OUTPUT:
輸出 str 排列後，為質數的數量

先根據題目範圍建質數表 1 ~ 10000000
接著跑 dfs ，找出所有可能的排列並存入 result
最後計算質數的數量

	#include <iostream>
	#include <vector>
	#include <sstream>
	#include <unordered_set>
	#include <algorithm>

	using namespace std;

	vector<bool> is_prime;
	unordered_set<int> result;

	void find_prime()
	{
	is_prime.assign(10000000, true);
	is_prime[0] = is_prime[1] = false;

	for (int i = 2; i < 10000000; ++i)
	{
	if (is_prime[i])
	{
	for (int j = i << 1; j < 10000000; j += i) is_prime[j] = false;
	}
	}
	}

	void dfs(string str, string target, int now, int Max)
	{
	if (now == Max)
	{
	stringstream ss(target);
	int tmp;

	ss >> tmp;
	result.emplace(tmp);

	return;
	}

	for (size_t i = 0; i < str.size(); ++i)
	{
	auto s = str;
	s.erase(s.begin() + i);
	dfs(s, target + str[i], now + 1, Max);
	}
	}

	int main()
	{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	// find all prime number between 1 ~ 10000000
	find_prime();

	int N;
	string str;
	cin >> N;

	while (N-- && cin >> str)
	{
	result.clear();
	int cnt = 0;

	// use dfs to find all permutation of str
	for (size_t i = 1; i <= str.size(); ++i) dfs(str, "", 0, i);
	for (auto& i : result) if (is_prime[i]) ++cnt;

	cout << cnt << "\n";
	}

	return 0;
	}