爱奇艺 回文素数 数学

题目描述

如果一个整数只能被1和自己整除,就称这个数是素数。
如果一个数正着反着都是一样,就称为这个数是回文数。例如:6, 66, 606, 6666
如果一个数字既是素数也是回文数,就称这个数是回文素数
牛牛现在给定一个区间[L, R],希望你能求出在这个区间内有多少个回文素数。

输入描述:

输入包括一行,一行中有两个整数(1 ≤ L ≤ R ≤ 1000)

输出描述:

输出一个整数,表示区间内回文素数个数。

示例1

输入

100 150

输出

2

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e3+5;
int vis[maxn];
void is_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<maxn;++i)
    {
        if(!vis[i]) continue;
        for(int j=2;j*i<maxn;++j)
        {
            vis[i*j]=0;
        }
    }
}
void is_rev()
{
    int s[5];
    int top;
    is_prime();

    for(int i=1;i<maxn;++i)
    {
        if(vis[i])
        {
            top=0;
            int num=i;
            while(num)
            {
                s[top++]=num%10;
                num/=10;
            }
            int flag=0;
            for(int i=0;i<top/2;++i)
            {
                if(s[i]!=s[top-i-1])
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
            {
                vis[i]=0;
            }
        }
    }
}
int main()
{
    int l,r;
    is_rev();
    while(cin>>l>>r)
    {
        int cnt=0;
        for(int i=l;i<=r;++i)
        {
            if(vis[i])cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}