题目描述

解析：关于回文数与质数的判断比较简单，但是这一题需要解决的是性能问题。

因为范围是在1亿以内，如果使用遍历再循环判断质数的方法则会造成超时无法全AC。于是利用数组is_prime[MAX_N]保存素数判断，用空间来节省时间。需要注意的是还要在遍历的过程中判断数组是否越界，因为测试数据中还有大于1亿的测试点。（坑人！！）

#include <bits/stdc++.h>
using namespace std;

const int MAX_N=10000005;
bool is_prime[MAX_N];

void init()
{
    memset(is_prime,true,sizeof(is_prime));
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i*i<=MAX_N;i++)
    {
        if(!is_prime[i])continue;
        for(int j=i+i;j<MAX_N;j+=i)
        {
            is_prime[j]=false;
        }
    }
}

bool ishw(int q)
{
    int num = 0;
    int p = q;
    while(p != 0)
    {
        num = num * 10 + p % 10;
        p = p / 10;
    }
    if(num != q)
    {
        return 0;
    }
    return 1;
}

int main()
{
    init();
    int a,b;
    cin>>a>>b;
    int m = 0;
    if(a % 2 == 0)
    {
        m++;
    }
    for(int i = a + m; i <= b ; i += 2)
    {
        if(i>=MAX_N)continue;
        if(ishw(i) && is_prime[i])
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

然而题目下面还有提示，根据提示的方法做可以提高效率。

说明

先产生回文数再判断是否为素数

#include <bits/stdc++.h>
using namespace std;

bool ispan(int q)
{
    for(int i = 2; i <= sqrt(q) ; i++)
    {
        if(q % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int a,b;
    cin>>a>>b;
    vector<int> vec;
    int item;
    //长度为1
    for(int d1 = 5 ; d1 < 10 ; d1++)
    {
        vec.push_back(d1);
    }
    //长度为2
    for(int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        item = 10*d1 + d1;
        vec.push_back(item);
    }
    //长度为3
    for (int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            item = 100*d1 + 10*d2 + d1;//(处理回文数...)
            vec.push_back(item);
        }
    }
    //长度为4
    for(int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            item = 1000*d1 + 100*d2 + 10*d2 + d1;
            vec.push_back(item);
        }
    }
    //长度为5
    for (int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
                item = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
                vec.push_back(item);
            }
        }
    }
    //长度为6
    for(int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
                item = 100000*d1 + 10000*d2 + 1000*d3 + 100*d3 + 10*d2 + d1;
                vec.push_back(item);
            }
        }
    }
    //长度为7
    for (int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
                for (int d4 = 0; d4 <= 9; d4++) {
                    item = 1000000*d1 + 100000*d2 + 10000*d3 + 1000*d4 + 100*d3 + 10*d2 + d1;//(处理回文数...)
                    vec.push_back(item);
                }
            }
        }
    }
    //长度为8
    for(int d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
        for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
                for (int d4 = 0; d4 <= 9; d4++) {
                    item = 10000000*d1 + 1000000*d2 + 100000*d3 + 10000*d4 + 1000*d4 + 100*d3 + 10*d2 + d1;
                    vec.push_back(item);
                }
            }
        }
    }
    for(auto c : vec)
    {
        if( c >= a && c <= b && ispan(c))
        {
            cout<<c<<endl;
        }
    }
    return 0;
}