[USACO1.5]回文质数 Prime Palindromes

coldheart 收录于算法

2018-08-07 约 355 字预计阅读 1 分钟

题目描述

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。

写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数

输入格式

第 1 行: 二个整数 a 和 b .

输出格式

输出一个回文质数的列表，一行一个。

输入样例

5 500

输出样例

5 7 11 101 131 151 181 191 313 353 373 383

思路

建立两个函数分别判断质数和回文数

质数判断用枚举或埃氏筛选法，回文判断只要将数字倒过来与原数字比较

但是直接交，不管哪个函数先运行，都会吃T（虽然先判断回文整个程序能更快）。因此要~~投机取巧~~优化：拥有偶数数位的质数不可能是回文数，所以可以选择直接忽略10^8^到10^9^之间的数，就正好不被TLE

代码

#include<bits/stdc++.h>
using namespace std;
bool is_Prime(int x)
{
    if(x<=1) return false;
    int sqr=(int)sqrt(1.0*x);
    for(int i=2;i<=sqr;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}
bool is_Palindromes(int x)
{
    int t=x,x1=0;
    while (t!=0)
    {
        x1=x1*10+t%10;
        t/=10;
    }
    if (x1==x) return true;
    else return false;
}
int main()
{
    int ans=0;
    int a,b;
    cin>>a>>b;
    if(b>10000000) b=10000000;
    for(int i=a;i<=b;i++)
    {
        if(is_Palindromes(i))
        {
            if(is_Prime(i))
                cout<<i<<endl;
        }
    }
    return 0;
}