学步园

【USACO1.5.2】Prime Palindromes 回文质数

Time Limit:10000MS  Memory Limit:65536K
Total Submit:84 Accepted:43 
Case Time Limit:1000MS

Description

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。 
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;

Input

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

Output

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

Sample Input

5 500

Sample Output

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

Hint

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: 要产生正确的回文数，你可能需要几个像下面这样的循环。

产生长度为5的回文数:

  for (d1 = 1; d1 <= 9; d1+=2) {	// 只有奇数才会是素数

     for (d2 = 0; d2 <= 9; d2++) {

         for (d3 = 0; d3 <= 9; d3++) {

           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)

         }

     }

 }

解题思路：

这题··，用素数筛就爆内存，用一般的素数判别法，最后一个数据就T，所以在网上看了别人的代码，用的vector，自己先前不会用vector，顺便用这个学习下了

/*
 ID:wikioi_2
 PROG: pprime
 LANG: C++
 */


#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
# include<algorithm>

using namespace std;

ifstream fin("pprime.in");
ofstream fout("pprime.out");

bool is_prime(int num);

vector<int>result;
int a,b;

void dfs(int num,int len)
{
    if(len>8)
        return;

    if(is_prime(num))
       result.push_back(num);

    int factor = 1;

    for(int i=0;i<len;++i)
        factor*=10;

    for(int i=0;i<10;++i){
        //左右各加一个i
        int temp = factor*i;
        temp+=num;
        temp*=10;
        temp+=i;
        dfs(temp,len+2);
    }
}

void solve()
{
    in>>a>>b;

    for(int i=0;i<10;++i)
        dfs(i,1);

    //11直接加了
    result.push_back(11);

    sort(result.begin(),result.end());

    for(int i=0;i<result.size();++i)
        if(result[i]>=a&&result[i]<=b)
        out<<result[i]<<endl;
}

// num>=2
bool is_prime(int num)
{
    if(num==2) return true;

    int root = (int) sqrt(num);

    for(int i=2;i<=root;++i)
        if(num%i==0)
            return false;

    return true;
}


int main()
{
  solve();
  return 0;
}