【欧拉计划】41. Pandigital prime

（本题取 $n=9$）

【思路】$\mathcal O(n!)$ 构造全排列并判断是否为质数。由于 $n$ 较大，因此不宜使用欧拉筛。程序的时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$：

#include<stdio.h>
#include<stdbool.h>
#include<string.h>
int ans,a[10];
bool vis[10];
bool prime(int x)
{
    if(x<2)return false;
    if(x==2||x==3||x==5)return true;
    if(x%2==0||x%3==0||x%5==0)return false;
    for(int a=7,b=11;a*a<=x;a+=6,b+=6)if(x%a==0||x%b==0)return false;
    return true;
}
void dfs(int k,int n)
{
    if(k>n)
    {
        int x=0;
        for(int i=1;i<=n;++i)x=x*10+a[i];
        if(prime(x)&&x>ans)ans=x;
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if(vis[i])continue;
        a[k]=i;
        vis[i]=true;
        dfs(k+1,n);
        vis[i]=false;
    }
}
int main()
{
    for(int i=1;i<=9;++i)
    {
        memset(vis,false,sizeof(vis));
        dfs(1,i);
    }
    printf("%d",ans);
    return 0;
}