USACO 1.5 Prime Palindromes

Prime Palindromes

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

PROGRAM NAME: pprime

INPUT FORMAT

Line 1:

Two integers, a and b

SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out)

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


题目大意：给你一段区间a,b；问你在这个区间（包含ab）有多少个回文质数，数据范围10^8
思路：题面很简单，数据很感人。。。筛法是不行了，空间不太够（后来证明筛法是可行的10^8的bool是100Mb，用位运算压缩的话可以变成13Mb，时间上次点，然后发现没必要存储偶数，又可以压缩一半，总之各种压缩）。不能枚举质数的话只能枚举回文数了，一开始的想法是分段写，10^7以内的数据用筛法，查询O1，但是超过10^7的数据还是需要构造回文数，怎么构造呢，问题就出现了，枚举每一位的值再判断是否回文好麻烦，而且费时，后来想到可以倒过来做，确定一个回文数字前半段后，后半段就可以直接写出来，于是就直接1到10000循环构造就是了，因为构造出来不是排好序的，而是穿插的，于是存储起来，输出前排序，确定这个方法后，好简单，也不用分段了，直接暴力。

  1 /*
  2 ID:fffgrdc1
  3 PROB:pprime
  4 LANG:C++
  5 */
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<iostream>
  9 #include<algorithm>
 10 #include<string>
 11 #include<cmath>
 12 using namespace std;
 13 const int maxn=10000;
 14 bool bo[10005];
 15 int prime[5000],cnt=0;
 16 int ans[20000],tot=0;
 17 int transodd(int x)
 18 {
 19     string s="";
 20     while(x)
 21     {
 22         s=char(x%10+'0')+s;
 23         x/=10;
 24     }
 25     int len=s.length();
 26     for(int i=0;i<len-1;i++)
 27     {
 28         s=s+s[len-2-i];
 29     }
 30     len=len*2-1;
 31     x=0;
 32     for(int i=0;i<len;i++)
 33     {
 34         x=x*10+int(s[i]-'0');
 35     }
 36     //cout<<x;
 37     return x;
 38 }
 39 int transeven(int x)
 40 {
 41     string s="";
 42     while(x)
 43     {
 44         s=char(x%10+'0')+s;
 45         x/=10;
 46     }
 47     int len=s.length();
 48     for(int i=0;i<len;i++)
 49     {
 50         s=s+s[len-1-i];
 51     }
 52     len=len*2;
 53     x=0;
 54     for(int i=0;i<len;i++)
 55     {
 56         x=x*10+int(s[i]-'0');
 57     }
 58     //cout<<x;
 59     return x;
 60 }
 61 bool check(int x)
 62 {
 63     if(x<=maxn)return !bo[x];
 64     int temp=sqrt(double(x));
 65     for(int i=1;i<=cnt&&prime[i]<=temp;i++)
 66         if(!(x%prime[i]))return 0;
 67     return 1;
 68 }
 69 int main()
 70 {
 71     freopen("pprime.in","r",stdin);
 72     freopen("pprime.out","w",stdout);
 73     memset(bo,0,sizeof(bo));
 74     bo[0]=bo[1]=1;
 75     for(int i=2;i<maxn;i++)
 76     {
 77         if(!bo[i])
 78         {
 79             for(int j=2;i*j<maxn;j++)
 80             {
 81                 bo[i*j]=1;
 82             }
 83             prime[++cnt]=i;
 84         }
 85     }
 86     int a,b;
 87     scanf("%d%d",&a,&b);
 88     for(int i=1;i<10000;i++)
 89     {
 90         //printf("%d ",i);
 91         int x=transodd(i);
 92         //printf("%d ",x);
 93         if(x>=a&&x<=b)
 94         {
 95             if(check(x))ans[++tot]=x;
 96         }
 97         x=transeven(i);
 98         //printf("%d
",x);
 99         if(x>=a&&x<=b)
100         {
101             if(check(x))ans[++tot]=x;
102         }
103     }
104     sort(ans+1,ans+tot+1);
105     for(int i=1;i<=tot;i++)
106         printf("%d
",ans[i]);
107     return 0;
108 }

warning！！！接下来涉及到严重的剧透

后来看了别人的题解，发现偶数长度的回文串一定是11的倍数，一定不是质数（11除外），这样的话又可以优化一倍，而且用我写的代码在构建的时候可以不构建偶数长度的回文，这样可以保证数据是递增的，连最后的排序都可以省掉。。。。。大致就这样了