题目描述

151 既是一个质数，又是一个回文数，因此它可以被称为回文质数。

现在给定两个整数 a,b ，请你找出在 [a,b] 范围内的所有回文质数。

样例

输入样例：
5 500
输出样例：
5
7
11
101
131
151
181
191
313
353
373
383

算法1

(暴力枚举) $O(n^2)$

去掉偶数的校验，试出了在10^8内的最大回文质数

时间复杂度

参考文献

C++ 代码

#include <stdio.h>
#include <math.h>
int ishuiwen(int n);
int iszhishu(int n);

int main()
{
    int a,b,i;
    scanf("%d %d",&a,&b);
    if(a%2==1)
        i=a;
    else
        i=a+1;  

    if(b>9989899)   //平淡无奇的这一句，绝对精髓所在呀 
        b=9989899;
    for(;i<=b;i++,i++)  
        if(ishuiwen(i)&&iszhishu(i))
        printf("%d\n",i);   

    return 0;
}

int ishuiwen(int n)
{
    int a=n;
    int b,sum=0;
    while(a)
    {
        b=a%10;
        sum=sum*10+b;
        a=a/10;
    }
    if(sum==n)
        return 1;
    else
        return 0;
}


int iszhishu(int n)
{
    int a=(int)sqrt((double)n);
    int i;
    int flag=1;
    for(i=2;i<=a;i++)
        if(n%i==0)
        {
            flag=0;
            break;
        }
    return flag;            
}