首页 > 代码库 > poj3247:回文素数

poj3247:回文素数

总时间限制: 5000ms 内存限制: 65536kB描述一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数,如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。(注:不考虑超过整型数范围的情况)。输入位数n,其中1<=n<=9。输出第一行输出满足条件的素数个数。第二行按照从小到大的顺序输出所有满足条件的素数,两个数之间用一个空格区分。样例输入1样例输出42 3 5 7

 

 

 

这道题挺简单的,本来自己是肯定能够想到平方根为界限的,我开始自己傻了吧唧的,想减少判断过程所需的时间,于是想要初始化的时候预处理出所有小于1000000000是否为素数的标记

结果估计初始化的过程就超时了。。。

直接贴代码了,这太简单了。。。

#include <iostream>#include <queue>#include <stdio.h>using namespace std;const int MAX = 1000000000;int n;queue<int> q;int m[10]={0};int coun = 0;bool OK(int k){    if(k <= 1)        return false;    for(int i = 2; i * i <= k; i++)    {        if(k%i == 0)            return true;    }    return false;}void work(int i){    if(i == n)    {        int res = 0;        for(int j = 0; j < n; j++)        {            res *= 10;            res += m[j];         }         if(OK(res))         {             q.push(res);             coun++;         }         return ;    }    if( i < n/2 || ( n%2!=0 && i < n/2+1 ) )    {        for(int j = 0; j < 10; j++)        {            if(i == 0 &&((j == 0 || j == 2 || j == 5 || j == 4 || j == 6 || j == 8)&&n>1) )            {                continue;            }            m[i] = j;            work(i+1);        }    }    else    {            m[i] = m[n-1-i];            work(i+1);    }}int main(){    scanf("%d",&n);    work(0);    printf("%d\n",coun );    for(int i = 0; i < coun; i++)    {        int res = q.front();        q.pop();        printf("%d ", res);    }    printf("\n");    return 0;}