POJ 3842 排列问题

给定几个数，求其排列

排列问题可以转化为递归搜索~

低位安排不同的数，求剩下的数的排列，再递归

效果还不错，时间效率暂时第一啊，还是我在poj的首次哦

http://poj.org/problemstatus?problem_id=3842

#include <iostream>
using namespace std;
int prime[5000],pn,num[10],res,tab[10],sl;
bool p[10000];
void get()
{
    pn = 0;
    memset(p,true,sizeof(p));
    p[0] = p[1] = false;
    int i,j;
    for(i = 2;i < 10000;i ++)
    {
        if(!p[i])continue;
        for(j = i+i;j < 10000;j += i)
            p[j] = false;
    }
    for(i = 2;i < 10000;i ++)
        if(p[i])prime[pn++] = i;
}
bool test(int x)
{
    int i;
    int n = 0;
    for(i = x-1;i >= 0;i --)
        n = n*10 + tab[i];
//    printf("%d\n",n);
    if(n < 10000)
        return p[n];
    for(i = 0;prime[i]*prime[i] <= n; i ++)
    {
        if(n % prime[i] == 0)return false;
    }
    return true;
}
void search(int x)
{
//    printf("%d %d\n",x,sl);
    if(tab[x-1] != 0 && test(x))
        res ++;
    if(x == sl)return;
    int i;
    for(i = 0;i < 10;i ++)
    {
        if(num[i] == 0)continue;
        num[i] --;
        tab[x] = i;
        search(x+1);
        num[i] ++;
    }
}
int main()
{
    int c,i;
    char s[10];
    scanf("%d",&c);
    get();
    while(c--)
    {
        scanf("%s",&s);
        sl = strlen(s);
        memset(num,0,sizeof(num));
        for(i = 0;s[i] != '\0';i ++)
            num[s[i]-'0']++;
        res = 0;
        if(num[2])res++;
        for(i = 0;i < 10;i ++)
        {
            if(i%2 == 0)continue;
            if(num[i] == 0)continue;
            num[i] --;
            tab[0] = i;
            search(1);
            num[i] ++;
        }
        printf("%d\n",res);
    }
    return 0;
}