[USACO1.5]回文质数 Prime Palindromes

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

5 500

输出样例#1：

5

7

11

101

131

151

181

191

313

353

373

383

说明

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cstring>

#include<sstream>

#include <algorithm>

using namespace std;

const int  maxn=9989999;   //小小的cheat 打表看到最大是9989899

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;

            }

        }

    }

}

巴特西

[USACO1.5]回文质数 Prime Palindromes

最新文章

热门文章