学步园

【USACO1.5.3】Superprime Rib 特殊的质数肋骨

Time Limit:10000MS  Memory Limit:65536K
Total Submit:56 Accepted:44 
Case Time Limit:1000MS

Description

农民约翰的母牛总是产生最好的肋骨。 你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73
是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。 数字1不被看作一个质数。

Input

单独的一行包含N。

Output

按顺序输出长度为 N 的特殊质数,每行一个。

Sample Input

4

Sample Output

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

解题思路：

这道题不怎么难，就是说，输入一个长度n，然后依次把这个长度为n的数字从右向左递减1位，并且保证每次递减完后形成的数字必须还是素数，就用最为普通的判素方法就可以了，关于产生数，一定要明确，因为在n-1次运算后，最左边的一位数字会单独作为一个数字出现，那么要想要最终的结果是素数，那么这个数字必须也得是素数，所以，我们只需要枚举2,3,5,7开头的数字就OK了。因为题目中说了N<=8，关于生成数字就用到递归的思想吧。

还要说明的一点是，偶数一定不是素数（除了2意外），奇数有可能是素数，所以我们在pd的过程中，只需要每次枚举所产生的奇数位就可以了~

代码：

/*
ID:wikioi_2
PROG:sprime
LANG:C++
*/

# include<cstdio>
# include<iostream>
# include<cmath>

using namespace std;

int n;
int a[] = {0,1,3,5,7,9};

int pd_prime( int x )
{
    if ( x==2 )
        return 1;
    int root = sqrt(x+0.5);
    for ( int i = 2;i <= root;i++ )
    {
        if ( x%i==0 )
            return 0;
    }
    return 1;
}

void f( int x,int y )
{
    if ( y==n )
    {
        cout<<x<<endl;
        return;
    }

    for ( int i = 0;i < 6;i++ )
    {
        if ( pd_prime(x*10+a[i]) )
        {
            f( x*10+a[i],y+1);
        }
    }


}


int main(void)
{
    //int n;
    freopen("sprime.in","r",stdin);
    freopen("sprime.out","w",stdout);
    cin>>n;
    f(2,1);
    f(3,1);
    f(5,1);
    f(7,1);


    return 0;
}