洛谷P1217 回文质数

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

5 500

输出 #1复制

5

7

11

101

131

151

181

191

313

353

373

383

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cstring>

#include<sstream>

#include <algorithm>

using namespace std;

const int  maxn=9989999;

bool isprime[maxn];

void prime(int o);

bool hw(string tem);

int main()

{

  int a,b;

  cin>>a>>b;

  if(b>maxn) b=maxn-1;

  prime(b);

  for(int i=a;i<=b;i++)

  {

      if(isprime[i]) {

        stringstream ob;

        ob<<i;

        string y;

        ob>>y;

        if(hw(y))printf("%d\n",i);

    }

  }

}

bool hw(string tem)

{

    string w=tem;

    reverse(w.begin(),w.end());

    return (w==tem);

}

void prime(int w){

    for(int i=0;i<=w;i++) isprime[i]=true;//先全部置为真

    isprime[0]=isprime[1]=false;//1 0 不是素数

    for(int i=2;i<=w;i++){//从2开始往后筛

        if(isprime[i]){

            for(int j=2*i;j<=w;j+=i){

                isprime[j]=false;

            }

        }

    }

}

巴特西

洛谷P1217 回文质数

最新文章

热门文章