2019-03-22 [蓝桥杯][算法提高VIP]特殊的质数肋骨

题目描述
农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始切下肋骨，每次还剩下的肋骨上的数字都组成一个质数。

例如有四根肋骨的数字分别是：7 3 3 1，那么全部肋骨上的数字 7331是质数；三根肋骨 733是质数；二根肋骨 73 是质数；当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。

写一个程序对给定的肋骨的数目 N (1< =N< =8),求出所有的特殊质数。数字1不被看作一个质数。
输入
单独的一行包含N。
输出
按顺序输出长度为 N 的特殊质数,每行一个。
样例输入
4
样例输出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
/*
const int N=100000000;
bool p[N];
int prime[10000000],cnt;
void FindPrime(int n)
{
    p[1]=true;//根据题意设定 
    for(int i=2;i<=n;i++)
    {
        if(p[i]==false) 
        {
            prime[++cnt]=i;
            for(int j=i+i;j<=n;j+=i) p[j]=true;
        }
    }
}
*/
int b[10],a[20][20];
int main(void)
{
    /*
    freopen("D:\\res.txt","w",stdout);
    for(int n=1;n<=8;n++)
    {
        int num=0;
        int x=1,y=9;
        for(int i=1;i<=n-1;i++) x*=10;
        for(int i=1;i<=n-1;i++) y=y*10+9;
        //cout<<x<<" "<<y<<endl;
        FindPrime(y); 
        int p1=lower_bound(prime+1,prime+cnt+1,x)-prime;
        int p2=cnt;
        for(int i=p1;i<=p2;i++)
        {
            int sum=0;
            bool yes=true;
            int d=prime[i];
            //判断是否是满足要求的特殊质数
            for(int j=1;j<=n;j++)
            {
                if(p[d])
                {
                    yes=false;
                    break;  
                }
                d/=10;  
            } 
            //if(yes) cout<<prime[i]<<endl;
            if(yes)
            {
                printf("a[%d][%d]=%d;\n",n,num++,prime[i]);
            }
        }
        printf("b[%d]=%d;\n",n,num);
    }
    */
    a[1][0]=2;
    a[1][1]=3;
    a[1][2]=5;
    a[1][3]=7;
    b[1]=4;
    a[2][0]=23;
    a[2][1]=29;
    a[2][2]=31;
    a[2][3]=37;
    a[2][4]=53;
    a[2][5]=59;
    a[2][6]=71;
    a[2][7]=73;
    a[2][8]=79;
    b[2]=9;
    a[3][0]=233;
    a[3][1]=239;
    a[3][2]=293;
    a[3][3]=311;
    a[3][4]=313;
    a[3][5]=317;
    a[3][6]=373;
    a[3][7]=379;
    a[3][8]=593;
    a[3][9]=599;
    a[3][10]=719;
    a[3][11]=733;
    a[3][12]=739;
    a[3][13]=797;
    b[3]=14;
    a[4][0]=2333;
    a[4][1]=2339;
    a[4][2]=2393;
    a[4][3]=2399;
    a[4][4]=2939;
    a[4][5]=3119;
    a[4][6]=3137;
    a[4][7]=3733;
    a[4][8]=3739;
    a[4][9]=3793;
    a[4][10]=3797;
    a[4][11]=5939;
    a[4][12]=7193;
    a[4][13]=7331;
    a[4][14]=7333;
    a[4][15]=7393;
    b[4]=16;
    a[5][0]=23333;
    a[5][1]=23339;
    a[5][2]=23399;
    a[5][3]=23993;
    a[5][4]=29399;
    a[5][5]=31193;
    a[5][6]=31379;
    a[5][7]=37337;
    a[5][8]=37339;
    a[5][9]=37397;
    a[5][10]=59393;
    a[5][11]=59399;
    a[5][12]=71933;
    a[5][13]=73331;
    a[5][14]=73939;
    b[5]=15;
    a[6][0]=233993;
    a[6][1]=239933;
    a[6][2]=293999;
    a[6][3]=373379;
    a[6][4]=373393;
    a[6][5]=593933;
    a[6][6]=593993;
    a[6][7]=719333;
    a[6][8]=739391;
    a[6][9]=739393;
    a[6][10]=739397;
    a[6][11]=739399;
    b[6]=12;
    a[7][0]=2339933;
    a[7][1]=2399333;
    a[7][2]=2939999;
    a[7][3]=3733799;
    a[7][4]=5939333;
    a[7][5]=7393913;
    a[7][6]=7393931;
    a[7][7]=7393933;
    b[7]=8;
    a[8][0]=23399339;
    a[8][1]=29399999;
    a[8][2]=37337999;
    a[8][3]=59393339;
    a[8][4]=73939133;
    b[8]=5;
    int n;
    cin>>n;
    for(int i=1;i<=b[n];i++) cout<<a[n][i-1]<<endl;
    return 0;   
}