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)

5711101131151181191313353373383 题目大意：给你一段区间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
     
        7 #include
      
         8 #include
       
          9 #include
        
          10 #include
         
           11 #include
          
            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
           
            =a&&x<=b) 94 { 95 if(check(x))ans[++tot]=x; 96 } 97 x=transeven(i); 98 //printf("%d\n",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\n",ans[i]);107 return 0;108 }
           
          
         
        
       
      
     

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

 

 

 

 

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