题目大意
给出 \(1\) 个数 \(n\)，求 \(n\) 的各位拆分后重新排列组合得到新数是质数的个数。
思路（欧拉筛，全排列）
对于求质数，与其每组数据运行 \(1\) 次质数筛，不如在一开始就筛出 \([1,10^7]\) 内的所有质数，用 bool 数组统计起来，这样只需运行 \(1\) 次质数筛，大大节约了时间。
对于筛法，这里使用时间复杂度为 \(O(n)\) 的线性筛（欧拉筛），模板如下：
inline void ola(int n){//欧拉筛
isprime[1]=false;//1不是质数
for(int i=2;i<=n;i++) isprime[i]=true;//默认都是质数
for(int i=2;i<=n;i++){//从2开始筛
if(isprime[i]) p[++t]=i;//是质数
for(int j=1;j<=t&&i*p[j]<=n;j++){
isprime[p[j]*i]=false;//如果这个数是质数，那么它的倍数肯定不是质数
if(i%p[j]==0) break;
}
}
}
接下来，我们可以分解 \(n\) 的每一位，用数组存起来，使用 next_permutation 进行全排列，最后得出新数判断即可，时间复杂度 \(O(t (\log_{10} n)!)\)。
注意：
-
有多组数据。
-
排列组成的第一个数不能为 \(0\)。
参考代码（请勿抄袭）：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+10;
bool isprime[MAXN];
int p[MAXN],t,n,s[10];
inline void ola(int n){//欧拉筛
isprime[1]=false;//1不是质数
for(int i=2;i<=n;i++) isprime[i]=true;//默认都是质数
for(int i=2;i<=n;i++){//从2开始筛
if(isprime[i]) p[++t]=i;//是质数
for(int j=1;j<=t&&i*p[j]<=n;j++){
isprime[p[j]*i]=false;//如果这个数是质数，那么它的倍数肯定不是质数
if(i%p[j]==0) break;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ola(10000000);//筛出质数
cin>>t;
while(t--){
cin>>n;
int tot=0,ans=0;
while(n){//分解各位
s[++tot]=n%10;
n/=10;
}
sort(s+1,s+tot+1);//从小到大排
do{
if(!s[1]) continue;//排列组成的第一个数不能为0
int QwQ=0;
for(int i=1;i<=tot;i++){
QwQ*=10;
QwQ+=s[i];//得出新数
}
if(isprime[QwQ]) ans++;//如果是质数，答案加1
}while(next_permutation(s+1,s+tot+1));
cout<<ans<<endl;
}
return 0;
}