题目描述

一个质数如果从个位开始，依次去掉一位数字，两位数字，三位数字。。。。。。直到只剩一位数字中间所有剩下的数都是质数，则称该质数为一个超级质数。例如：2333是一个质数，因为2333,233,23,2都是质数，所以2333是一个四位超级素数。请你写一个程序，给定一个整数X，求大小小于X的超级质数。

输入输出格式

输入格式：

一行，给出一个整数X(1<=X<=100000000).

输出格式：

第一行，一个整数k，表示X以内超级质数的个数.

第2至k+1行，每行一个整数，输出所有X以内的超级质数，这些数按从小到大的顺序排列。

输入输出样例

100

132357232931375359717379

说明

对于30%的数据，X<=1000。

对于100%的数据，X<=100000000。

本题可采用队列思想。首先将0放入队列中，接下来不断从队列中取出一个超级质数（或者是0）在其末尾添加0到9的数字后判断新数是否为超级质数，是就入队。最后在所有入过队的数中，输出X以内的数。还可以保证输出是有序的。

#include <cstdio>#include <cmath>#include <iostream>#include <cstdlib>using namespace std;int q[100],head=0,tail=1,cnt;int isprime(int x){    if(x<2) return 0;    int i;    for(i=2;i*i<=x;i++)    {        if(x%i==0) return 0;    }    return 1;}int main(){    int a,i,x;    scanf("%d\n",&x);    q[head]=0;    while(head<tail)    {        a=q[head];        if(a>100000000) break;        for(int i=1;i<=9;i++)        {            if(isprime(a*10+i))            {                q[tail++]=a*10+i;            }        }        head++;    }    for(i=1;i<tail;i++)    {        if(q[i]<x) cnt++;    }    printf("%d\n",cnt);    for(i=1;i<=cnt;i++)    {        printf("%d\n",q[i]);    }    return 0;}

超级质数