C++编程练习-回文素数


Description
一个数如果从左往右读和从右往左读数字是相同的，则称这个数是回文数，如121，1221，15651都是回文数。给定位数n，找出所有既是回文数又是素数的n位十进制数。（注：不考虑超过整型数范围的情况）。
Input
位数n,其中1<=n<=9。
Output
第一行输出满足条件的素数个数。
第二行按照从小到大的顺序输出所有满足条件的素数，两个数之间用一个空格区分。
Sample Input
1
Sample Output
4
2 3 5 7
参考代码
  1. #include <cstdio>   
  2. #include <cmath>   
  3. #include <cstdlib>   
  4. #include <string>   
  5. using namespace std;  
  6. int result[5960];  
  7. int r_s = 0;  
  8. int digit[10];  
  9. int a,b;  
  10. int pm[10000];  
  11. int pm_size = 0;  
  12. void init();  
  13. class MyString:public string{  
  14. public:  
  15.     MyString(int n);  
  16.     bool isPlalindrome();  
  17. private:  
  18.     string ds;  
  19. };  
  20. MyString::MyString(int n){  
  21.     while(n){  
  22.         char ch = (n % 10) + '0';  
  23.         n /= 10;  
  24.         ds.push_back(ch);  
  25.     }  
  26. }  
  27. bool MyString::isPlalindrome(){  
  28.     int len = ds.length();  
  29.     int mid = len / 2;  
  30.     for(int i = 0;i < mid; ++ i){  
  31.         if(ds[i] != ds[len - i - 1]){  
  32.             return false;  
  33.         }  
  34.     }  
  35.     return true;  
  36. }  
  37. void work( int c )  
  38. {  
  39.     int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;  
  40.     if ( c == 1 )  
  41.     {  
  42.         if ( a <= 2 && b >= 2 )  
  43.             result[r_s ++] = 2;  
  44.         if ( a <= 3 && b >= 3 )  
  45.             result[r_s ++] = 3;  
  46.         if ( a <= 5 && b >= 5 )  
  47.             result[r_s ++] = 5;  
  48.         if ( a <= 7 && b >= 7 )  
  49.             result[r_s ++] = 7;  
  50.         digit[c] = 4;  
  51.         return ;  
  52.     }  
  53.     for ( i = 0; i < p; i++ )  
  54.         s *= 10;  
  55.     for ( i = 1; i < 10; i += 2 )  
  56.     {  
  57.         for ( j = 0; j < s; j++ )  
  58.         {  
  59.             r = i * s + j;  
  60.             t1 = j / 10;  
  61.             t2 = p - 1;  
  62.             while ( t2 )  
  63.             {  
  64.             r = r * 10 + ( t1 % 10 );  
  65.             t1 /= 10;  
  66.             t2--;  
  67.             }  
  68.             r = r * 10 + i;  
  69.             if ( r < a )  
  70.             continue;  
  71.             if ( r > b ){  
  72.                 return ;  
  73.             }  
  74.             MyString s(r);  
  75.             if(s.isPlalindrome()){  
  76.                 bool bl = true;  
  77.                 for(int p = 0;p < pm_size && pm[p] < r;++ p){  
  78.                     if(r % pm[p] == 0){  
  79.                         bl = false;  
  80.                         break;  
  81.                     }  
  82.                 }  
  83.                 if(bl){  
  84.                     result[r_s ++] = r;  
  85.                     digit[c] ++;  
  86.                 }  
  87.             }  
  88.         }  
  89.     }  
  90. }  
  91.   
  92. int main( )  
  93. {  
  94.     int i, p, c;  
  95.     a = 2; b = 1000000000;  
  96.     p = 1;  
  97.     c = 0;  
  98.     init();  
  99.     while ( p < a )  
  100.     {  
  101.         c++;  
  102.         p *= 10;  
  103.     }  
  104.     p /= 10;  
  105.     while ( p < b )  
  106.     {  
  107.         if ( c == 2 )  
  108.         {  
  109.             digit[c] = 1;  
  110.             result[r_s ++] = 11;  
  111.         }  
  112.         if ( c & 1 )  
  113.             work( c );  
  114.         c++;  
  115.         p *= 10;  
  116.     }  
  117.     int n,start,end;  
  118.     scanf("%d",&n);  
  119.     printf("%d\n",digit[n]);  
  120.     start = (int)pow(10.0,n-1);  
  121.     end = (int)pow(10.0,n);  
  122.     for(i = 0;i < r_s;++ i){  
  123.         if(result[i] >= start && result[i] <= end){  
  124.             printf("%d ",result[i]);  
  125.         }  
  126.     }  
  127.     printf("\n");  
  128.     return 0;  
  129. }  
  130. void init(){  
  131.     for(int p = 2;p <= 100000;++ p){  
  132.         bool bl = true;  
  133.         for(int k = 2;k <= sqrt(1.0 * p);++ k){  
  134.             if(p % k == 0){  
  135.                 bl = false;  
  136.                 break;  
  137.             }  
  138.         }  
  139.         if(bl){  
  140.             pm[pm_size ++] = p;  
  141.         }  
  142.     }  
  143.     for(int i = 0;i < 10;++ i){  
  144.         digit[i] = 0;  
  145.     }  
  146. }  

相关内容